镇江网站建设策划,招聘网站页面设计图片,建设部网标准下载网站,公司改名字重新备案网站会停吗目录 LeetCode 322. 零钱兑换
LeetCode 279. 完全平方数
LeetCode 139. 单词拆分
总结 LeetCode 322. 零钱兑换
题目链接#xff1a;LeetCode 322. 零钱兑换
思想#xff1a;首先定义dp数组的含义#xff0c;dp[j]即总金额为j的情况下所需的最少的硬币个数。接下来确定…目录 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(vectorint coins, int amount) {vectorint 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) {vectorint 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, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool 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)。
总结
今天做的昏头昏脑还得是要多练习才行。
