今日任务

322. 零钱兑换

• 题目链接： https://leetcode.cn/problems/coin-change/description/
• 题目描述：
  

Code

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();// vector<vector<int>> memo(n, vector<int>(amount + 1, -1));// function<int(int, int)> dfs = [&](int i, int c) -> int{//     if(i < 0){//         return c == 0 ? 0 : INT_MAX / 2;//     }//     int &res = memo[i][c];//     if(res != -1){//         return res;//     }//     if(c < coins[i]){//         return res = dfs(i - 1, c);//     }//     return res = min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);// };// int ans = dfs(n - 1, amount);// return ans < INT_MAX /2 ? ans : -1;// dp[i][c] = min(dp[i - 1][c], dp[i][c - coins[i]] + 1)// dp[i + 1][c] = min(dp[i][c], dp[i + 1][c - coins[i]] + 1)// vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INT_MAX / 2));// dp[0][0] = 0;// for(int i = 0; i < n; i++){//     for(int c = 0; c <= amount; c++){//         if(c < coins[i]){//             dp[i + 1][c] = dp[i][c];//         }else{//             dp[i + 1][c] = min(dp[i][c], dp[i + 1][c - coins[i]] + 1);//         }//     }// }// return dp[n][amount] < INT_MAX / 2 ? dp[n][amount] : -1;// 优化// vector<vector<int>> dp(2, vector<int>(amount + 1, INT_MAX / 2));// dp[0][0] = 0;// for(int i = 0; i < n; i++){//     for(int c = 0; c <= amount; c++){//         if(c < coins[i]){//             dp[(i + 1) % 2][c] = dp[i % 2][c];//         }else{//             dp[(i + 1) % 2][c] = min(dp[i % 2][c], dp[(i + 1) % 2][c - coins[i]] + 1);//         }//     }// }// return dp[n % 2][amount] < INT_MAX / 2 ? dp[n % 2][amount] : -1;vector<int> dp(amount + 1, INT_MAX / 2);dp[0] = 0;for(int x : coins){for(int c = x; c <= amount; c++){dp[c] = min(dp[c], dp[c - x] + 1);}}return dp[amount] < INT_MAX / 2 ? dp[amount] : -1;}
};

279.完全平方数

• 题目链接： https://leetcode.cn/problems/perfect-squares/description/
• 题目描述：
  

Code

class Solution {
public:int numSquares(int n) {int end = sqrt(n);vector<vector<int>> memo(end + 1, vector<int>(n + 1, -1));function<int(int, int)> dfs = [&](int i, int c) -> int{if(i == 0){return c == 0 ? 0 : INT_MAX / 2;}int res = memo[i][c];if(res != -1){return res;}int x = i * i;if(c < x){return res = dfs(i - 1, c);}return res = min(dfs(i - 1, c), dfs(i, c - x) + 1);};return dfs(end, n);// vector<int> dp(n + 1, INT_MAX / 2);// dp[0] = 0;// for(int x = 1; x <= end; x++){//     for(int c = x * x; c <= n; c++){//         dp[c] = min(dp[c], dp[c - x * x] + 1);//     }// }// return dp[n];}
};

139.单词拆分

• 题目链接： https://leetcode.cn/problems/word-break/description/
• 题目描述：
  

Code

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(n + 1);dp[0] = true;for(int i = 1; i <= n; i++){for(int j = 0; j < i; j++){string word = s.substr(j, i - j);if(wordSet.contains(word)){dp[i] = dp[i] || dp[j];}}}return dp[n];}
};