dp06

322. 零钱兑换

class Solution {
public:int coinChange(vector<int>& coins, int amount) {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; j++){if (dp[j - coins[i]] != INT_MAX) {   dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == INT_MAX ? -1 : dp[amount];}
};

279. 完全平方数

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= 100; 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. 单词拆分
```C++
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());int n = s.size();vector<bool> dp(n + 1, false);dp[0] = true;for (int j = 1; j <= n; j++){for (int i = 0; i < j; i++){string word = s.substr(i, j - i);if (wordSet.find(word) != wordSet.end() && dp[i] == true){dp[j] = true;}}}return dp[n];}
};

多重背包

#include <iostream>
#include <vector>using namespace std;int main(){int c, n;cin >> c >> n;vector<int> w(n + 1, 0);vector<int> v(n + 1, 0);vector<int> k(n + 1, 0);for (int i = 0; i < n; i++) cin >> w[i];for (int i = 0; i < n; i++) cin >> v[i];for (int i = 0; i < n; i++) cin >> k[i];vector<int> dp(c + 1, 0);for (int i = 0; i < n; i++){for (int j = c; j >= w[i]; j--){for (int q = 1; (j - q * w[i] >= 0) && (q <= k[i]); q++){dp[j] = max(dp[j], dp[j - q * w[i]] +q * v[i]);}}}cout << dp[c];return 0;
}