题目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];
}
};
