代码随想录第二十天|动态规划（4）

目录

LeetCode 322. 零钱兑换

LeetCode 279. 完全平方数

LeetCode 139. 单词拆分

总结

---

LeetCode 322. 零钱兑换

题目链接：LeetCode 322. 零钱兑换

思想：首先定义dp数组的含义，dp[j]即总金额为j的情况下所需的最少的硬币个数。接下来确定dp数组的递推公式，即在总金额为j的情况下，所需要的硬币个数可以是当前值即dp[j]，也可以是减掉当前硬币面值的前一个dp[j-coins[i]] + 1的值。因为要求最小，所以取他俩的最小值。而关于dp数组的初始化，因为要求的值是最小值，所以所有的数都取INT_MAX；其次，dp数组的所有数都是根据dp[0]的值求出的，所以dp[0]要初始化为0，这有什么意义呢，其实也没啥意义。最后要确定循环的顺序，因为这里只需要找到最少的硬币个数，所以组合和排序的顺序都可以，其次这里是一个完全背包问题，所以容量要从小到大遍历。

代码如下：

    int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= amount; i++) {  // 遍历背包for (int j = 0; j < coins.size(); j++) { // 遍历物品if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX ) {dp[i] = min(dp[i - coins[j]] + 1, dp[i]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}

时间复杂度：O(n^2)，空间复杂度：O(n)。

LeetCode 279. 完全平方数

题目链接：LeetCode 279. 完全平方数

思想：首先确定dp数组含义，dp[j]即总和为j的完全平方的最少数量。dp的递推公式、初始化和循环遍历顺序跟上题一样。本题要注意一点就是在循环物品的种类的时候，要对n取平方根处理，这样才好计算完全平方数。

代码如下：

    int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;int size = sqrt(n);for (int i = 1; i <= size; i++) {int weight = i * i;for (int j = weight; j <= n; j++) {dp[j] = min(dp[j - weight] + 1, dp[j]);}}return dp[n];}

时间复杂度：O(n^2)，空间复杂度：O(n)。

LeetCode 139. 单词拆分

题目链接：LeetCode 139. 单词拆分

思想：本题确实没怎么搞懂，没把它化解成完全背包问题。遂看题解。首先dp数组的含义就是，长度为j的字符串是否可以用字典里面的字符串来拼接。递推公式，如果确定dp[j]是true，且[j,i]在这个区间的子串出现在字典里，那么dp[i]一定是true。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true）那么 dp[i] = true。从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。本题是求拼接成一个字符串，每个字典里的字符串的位置不固定，所以本题应该是排列数问题，所以先循环背包，再循环遍历物品。

代码如下：

    bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {for (int j = 0; j < i; j++) {string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j] == true) {dp[i] = true;}}}return dp[s.size()];}

时间复杂度：O(n^2)，空间复杂度：O(n)。

总结

今天做的昏头昏脑，还得是要多练习才行。