279. 完全平方数

这题和上篇文章的题类似，直接上代码

class Solution {
public:
    int numSquares(int n) {
        
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        //j表示背包容量，dp[j]表示和为n的完全平方数的最少数量
        for(int i=0;i*i<=n;i++)
        {
            for(int j=i*i;j<=n;j++)
            {
                if(dp[j-i*i]!=INT_MAX)
                    dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};

139. 单词拆分

 这题要想到截取区间，如果区间前的单词可以由wordDict中的单词构成，并且区间中的单词也可以在wordDict中查找到，那么当前索引前的单词就可由wordDict中的单词构成。对单词的顺序有要求，所以要先遍历背包后遍历物品。dp表示该索引前的单词是否可以由wordDict中的单词构成，下标代表索引。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> wordSet(wordDict.begin(),wordDict.end());
        //dp表示索引之前的单词是否出现在wordDict中
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();i++)
        {
            for(int j=0;j<i;j++)
            {
                string word=s.substr(j,i-j);
                //j之前的单词可以由wordDict中的单词构成
                //并且当前区间的单词可以查找到
                if(dp[j]!=false && wordSet.find(word)!=wordSet.end())
                {
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];
    }
};