代码随想录算法训练营第三十八天 | 动态规划 part06

class Solution {
public:int coinChange(vector<int>& coins, int amount) {// 1. dp[j]表示凑成j最少几个硬币// 2. dp[j] = min(dp[j], dp[j - coins[i]] + 1)// 3. 初始化为INT_MAX, dp[0] = 0// 4. 遍历顺序：因为这里既不是排序，也不是组合，所以遍历顺序无所谓vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for (int i = 0; i < coins.size(); ++i) {for (int j = coins[i]; j < amount + 1; j++) {if ( dp[j - coins[i]] != INT_MAX)dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}if (dp[amount] == INT_MAX)return -1;elsereturn dp[amount];}
};

class Solution {
public:int numSquares(int n) {// 1. dp[j]表示凑成j最少几个硬币// 2. dp[j] = min(dp[j], dp[j - i * i] + 1)// 3. 初始化为INT_MAX, dp[0] = 0// 4. 遍历顺序：因为这里既不是排序，也不是组合，所以遍历顺序无所谓vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i * i <= n; ++i) {for (int j = i * i; j < n + 1; j++) {if (dp[j - i * i] != INT_MAX)dp[j] = min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
};

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// 1. dp[j] 表示长度为j的字符能否由wordDict组成// 2. if (dp[i] == true && i-j是wordDict的一员) dp[j] = true // 3. 初始化为false，除了dp[0]// 4. 遍历顺序：先背包后物品。排列vector<bool> dp(s.size() + 1, false);dp[0] = true;unordered_set wordSet(wordDict.begin(), wordDict.end());for (int j = 0; j < s.size() + 1; ++j) {for (int i = 0; i < j; ++i) {string ij = s.substr(i, j - i);if (dp[i] == true && wordSet.find(ij) != wordSet.end())dp[j] = true;}}return dp[s.size()];}
};