算法训练营day38(12.6)

题目1： 322. 零钱兑换
代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int MAX = 999999;
        int m = coins.size();
        int n = amount;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, MAX));
        dp[0][0] = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++ ) {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]] + 1);
                }
            }
        }
        return dp[m][n] == MAX ? -1 : dp[m][n];
    }
};

题目2： 279. 完全平方数

class Solution {
public:
     int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

题目3： 139. 单词拆分

代码：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, bool> wordMap;
        for(auto x: wordDict) {
            wordMap[x] = true;
        }

        int n = s.length();
        vector<bool> dp(n + 1);
        dp[0] = true;

        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && wordMap.find(s.substr(j, i - j)) != wordMap.end()) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
};