Update

youngyangyang04 · youngyangyang04 · commit 2da3dacb2502 · 2020-12-01T09:16:49.000+08:00
diff --git a/README.md b/README.md
@@ -19,6 +19,7 @@
 * [KMP算法（代码篇）](https://www.bilibili.com/video/BV1M5411j7Xx)
 * [回溯算法（理论篇）](https://www.bilibili.com/video/BV1cy4y167mM)
 * [回溯算法之组合问题（力扣题目：77.组合）](https://www.bilibili.com/video/BV1ti4y1L7cv)
+* [带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）](https://www.bilibili.com/video/BV1wi4y157er)
 
 （持续更新中....）
 
@@ -241,6 +242,7 @@
 |[0056.合并区间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0056.合并区间.md) |数组 |中等| **贪心** 以为是模拟题，其实是贪心|
 |[0057.插入区间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0057.插入区间.md) |数组 |困难| **模拟**  是一道数组难题|
 |[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md) |数组 |中等|**模拟**|
+|[0070.爬楼梯](https://github.com/youngyangyang04/leetcode/blob/master/problems/0070.爬楼梯.md) |动态规划|简单|**动态规划** dp里求排列|
 |[0077.组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0077.组合.md) |回溯 |中等|**回溯**|
 |[0078.子集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0078.子集.md) |回溯/数组 |中等|**回溯**|
 |[0083.删除排序链表中的重复元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0083.删除排序链表中的重复元素.md) |链表 |简单|**模拟**|
@@ -304,6 +306,7 @@
 |[0347.前K个高频元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0347.前K个高频元素.md) |哈希/堆/优先级队列 |中等| **哈希/优先级队列**|
 |[0349.两个数组的交集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0349.两个数组的交集.md) |哈希表 |简单|**哈希**|
 |[0350.两个数组的交集II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0350.两个数组的交集II.md) |哈希表 |简单|**哈希**|
+|[0377.组合总和Ⅳ](https://github.com/youngyangyang04/leetcode/blob/master/problems/0377.组合总和Ⅳ.md) |动态规划 |中等|**完全背包** 求排列|
 |[0383.赎金信](https://github.com/youngyangyang04/leetcode/blob/master/problems/0383.赎金信.md) |数组 |简单|**暴力** **字典计数** **哈希**|
 |[0404.左叶子之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0404.左叶子之和.md) |树/二叉树 |简单|**递归** **迭代**|
 |[0406.根据身高重建队列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0406.根据身高重建队列.md) |树/二叉树 |简单|**递归** **迭代**|
@@ -323,6 +326,7 @@
 |[0501.二叉搜索树中的众数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0501.二叉搜索树中的众数.md) |二叉树 |简单|**递归/中序遍历**|
 |[0513.找树左下角的值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0513.找树左下角的值.md) |二叉树 |中等|**递归** **迭代**|
 |[0515.在每个树行中找最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0515.在每个树行中找最大值.md) |二叉树 |简单|**广度优先搜索/队列**|
+|[0518.零钱兑换II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0518.零钱兑换II.md) |动态规划 |中等|**动态规划** dp里求组合|
 |[0530.二叉搜索树的最小绝对差](https://github.com/youngyangyang04/leetcode/blob/master/problems/0530.二叉搜索树的最小绝对差.md) |二叉树搜索树 |简单|**递归** **迭代**|
 |[0538.把二叉搜索树转换为累加树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0538.把二叉搜索树转换为累加树.md) |二叉搜索树 |简单|**递归** **迭代**|
 |[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md) |字符串 |简单| **模拟**|
diff --git a/problems/0055.跳跃游戏.md b/problems/0055.跳跃游戏.md
@@ -1,8 +1,10 @@
-## 链接
-https://leetcode-cn.com/problems/jump-game/
+
+> 通知
 
 # 55. 跳跃游戏 
 
+题目链接：https://leetcode-cn.com/problems/jump-game/
+
 给定一个非负整数数组，你最初位于数组的第一个位置。
 
 数组中的每个元素代表你在该位置可以跳跃的最大长度。
@@ -24,18 +26,19 @@ https://leetcode-cn.com/problems/jump-game/
 
 刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？ 
 
-可以转变一下思路，不一样非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
+其实跳几步无所谓，关键在于可跳的覆盖范围！
 
-这个范围内，已经是可以跳过来的，别管是怎么跳的，反正一定可以跳过来。
+不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
 
-**那么就是这个跳跃覆盖范围究竟可不可以覆盖到终点！** 
+这个范围内，别管是怎么跳的，反正一定可以跳过来。
 
-每次移动取最大跳跃步数，得到最大的覆盖范围，每移动一个单位，就更新最大覆盖范围。 
+**那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！** 
 
-**局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到就是整体最大覆盖范围，看是否能到终点**。
+每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。 
 
+**贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点**。
 
-那么我们每次取最大的覆盖范围，看最后能否覆盖终点。
+局部最优推出全局最优，找不出反例，试试贪心！
 
 如图：
 
@@ -45,11 +48,11 @@ i每次移动只能在cover的范围内移动，每移动一个元素，cover得
 
 而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
 
-如果cover大于等于了终点下表，直接return true就可以了。
+如果cover大于等于了终点下标，直接return true就可以了。
 
 C++代码如下：
 
-```
+```C++
 class Solution {
 public:
     bool canJump(vector<int>& nums) {
@@ -65,6 +68,12 @@ public:
 ```
 # 总结
 
+这道题目关键点在于：不用拘泥于每次究竟跳跳几步，而是看覆盖范围，覆盖范围内已经是可以跳过来的，不用管是怎么跳的。
+
+大家可以看出思路想出来了，代码还是非常简单的。
+
+一些同学可能感觉，我在讲贪心系列的时候，题目和题目之间貌似没有什么联系？
 
+**是真的就是没什么联系，因为贪心无套路！**没有个整体的贪心框架解决一些列问题，只能是接触各种类型的题目锻炼自己的贪心思维！
 
-其实贪心和动态规划很容易混在一起，在面试中，我们应该本着能用贪心就用贪心，贪心解决不了再考虑用动态规划。 毕竟贪心更容易理解，并快速写出代码。
+就酱，「代码随想录」值得推荐给身边的朋友同学们！
diff --git a/problems/0070.爬楼梯.md b/problems/0070.爬楼梯.md
@@ -0,0 +1,19 @@
+
+dp里求排列，1 2 步  和 2 1 步都是上三个台阶，但不一样！
+
+这是求排列
+```
+class Solution {
+public:
+    int climbStairs(int n) {
+        vector<int> dp(n + 1, 0);
+        dp[0] = 1;
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= 2; j++) {
+                if (i - j >= 0) dp[i] += dp[i - j];
+            }
+        }
+        return dp[n];
+    }
+};
+```
diff --git a/problems/0122.买卖股票的最佳时机II.md b/problems/0122.买卖股票的最佳时机II.md
@@ -126,6 +126,9 @@ public:
 
 就酱，「代码随想录」是技术公众号里的一抹清流，值得推荐给你的朋友同学们！
 
+> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在公众号：[代码随想录](https://img-blog.csdnimg.cn/20201124161234338.png)，关注后就会发现和「代码随想录」相见恨晚！**
+
+**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
+
 
-> 我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
 
diff --git a/problems/0279.完全平方数.md b/problems/0279.完全平方数.md
@@ -0,0 +1,42 @@
+没有问你组合方式，而是问你最小个数
+
+// 组合的逻辑
+```
+class Solution {
+public:
+    int numSquares(int n) {
+        vector<int> sum;
+        for (int i = 1; i * i <= n; i++) {
+            sum.push_back(i * i);
+        }
+        vector<int> dp(n + 1, INT_MAX);
+        dp[0] = 0;
+        for (int i = 0; i < sum.size(); i++) {
+            for (int j = 1; j <= n; j++) {
+                if (j - sum[i] >= 0 && dp[j - sum[i]] != INT_MAX) {
+                    dp[j] = min(dp[j - sum[i]] + 1, dp[j]);
+                }
+            }
+        }
+        return dp[n];
+    }
+};
+```
+
+
+// 排列的逻辑
+```
+class Solution {
+public:
+    int numSquares(int n) {
+        vector<int> dp(n + 1, 0);
+        for (int i = 0; i <= n; i++) {
+            dp[i] = i; // 最多也就是i都是1组成的情况
+            for (int j = 1; j * j <= i; j++) {
+                dp[i] = min(dp[i - j * j] + 1, dp[i]);
+            }
+        }
+        return dp[n];
+    }
+};
+```
diff --git a/problems/0322.零钱兑换.md b/problems/0322.零钱兑换.md
@@ -20,8 +20,6 @@ public:
                     if (dp[i] == 0) dp[i] = dp[i - coins[j]] + 1;
                     else dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                 }
-
-
             }
             //for (int k = 0 ; k<= amount; k++) {
             //    cout << dp[k] << " ";
@@ -35,6 +33,28 @@ public:
 };
 ```
 
+我用求组合的思路也过了，
+```
+class Solution {
+public:
+    int coinChange(vector<int>& coins, int amount) {
+        //int dp[10003] = {0}; // 并没有给所有元素赋值0
+        //if (amount == 0) return 0;
+        vector<int> dp(10003, INT_MAX);
+        dp[0] = 0;
+        for (int i = 0 ;i < coins.size(); i++) { // 求组合
+            for (int j = 1; j <= amount; j++) {
+                if (j - coins[i] >= 0 && dp[j - coins[i]] != INT_MAX) {
+                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
+                }
+            }
+        }
+        if (dp[amount] == INT_MAX) return -1;
+        return dp[amount];
+    }
+};
+```
+
 这种标记d代码简短，但思路有点绕
 ```
 class Solution {
diff --git a/problems/0377.组合总和Ⅳ.md b/problems/0377.组合总和Ⅳ.md
@@ -0,0 +1,46 @@
+
+和之前个回溯法的各个总和串起来一波，本题用回溯稳稳的超时
+
+```
+class Solution {
+public:
+    int combinationSum4(vector<int>& nums, int target) {
+        vector<int> dp(target + 1, 0);
+        dp[0] = 1;
+        for (int i = 0; i <= target; i++) {
+            for (int j = 0; j < nums.size(); j++) {
+                if (i - nums[j] >= 0) {
+                    dp[i] += dp[i - nums[j]];
+                }
+            }
+        }
+        return dp[target];
+    }
+};
+```
+
+
+C++测试用例有超过两个树相加超过int的数据
+超限的情况 
+
+
+一些题解会直接用ull  usigned long long
+
+java 也是四个字节，理论上没有差别，可能后台java和C++测试用例不同，bug.....
+```
+class Solution {
+public:
+    int combinationSum4(vector<int>& nums, int target) {
+        vector<int> dp(target + 1, 0);
+        dp[0] = 1;
+        for (int i = 0; i <= target; i++) {
+            for (int num : nums) {
+                if (i - num >= 0 && dp[i] < INT_MAX - dp[i - num]) {
+                    dp[i] += dp[i - num];
+                }
+            }
+        }
+        return dp[target];
+    }
+};
+```
diff --git a/problems/0474.一和零.md b/problems/0474.一和零.md
@@ -1,13 +1,14 @@
 
-搞不懂 leetcode后台是什么牛逼的编译器，初始化int dp[101][101] = {0}; 可以 ，int dp[101][101];就不行，有其他默认值，坑死。
-代码我做了实验，后台会拿findMaxForm，运行两次，取第二次的结果，dp有上次记录的数值。
-
-```
 // 即使做了很多动态规划的题目，做这个依然懵逼
 // 这道题目有点 程序员自己给自己出难进急转弯的意思
 // 该子集中 最多 有 m 个 0 和 n 个 1 。 指的是整体子集
 // 这是二维背包，多重背包
 // dp[i][j] 有i个0，j个1最大有多少个子集，但是遍历的时候 顶部是哪里呢？
+
+搞不懂 leetcode后台是什么牛逼的编译器，初始化int dp[101][101] = {0}; 可以 ，int dp[101][101];就不行，有其他默认值，坑死。
+代码我做了实验，后台会拿findMaxForm，运行两次，取第二次的结果，dp有上次记录的数值。
+
+```
 class Solution {
 public:
     int findMaxForm(vector<string>& strs, int m, int n) {
diff --git a/problems/0518.零钱兑换II.md b/problems/0518.零钱兑换II.md
@@ -0,0 +1,41 @@
+
+// 计算有多少种方式
+// 完全背包 for循环的顺序啊，先是哪个for 后是哪个for定不下来
+
+排列
+```
+class Solution {
+public:
+    int change(int amount, vector<int>& coins) {
+        int dp[50001] = {0};
+        dp[0] = 1;
+        for (int i = 0; i <= amount; i++) {
+            for (int j = 0; j < coins.size(); j++) { // 这是组合把？？？
+                if (i - coins[j] >= 0) dp[i] += dp[i - coins[j]];
+            }
+            for (int j = 0; j <= amount; j++) {
+                cout << dp[j] << " ";
+            }
+            cout << endl;
+        }
+        return dp[amount];
+    }
+};
+```
+
+这个才是组合，本题的题解， 
+```
+class Solution {
+public:
+    int change(int amount, vector<int>& coins) {
+        int dp[50001] = {0};
+        dp[0] = 1;
+        for (int i = 0; i < coins.size(); i++) { // 一个钱币只在序列里出现一次
+            for (int j = 0; j <= amount; j++) {
+                if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
+            }
+        }
+        return dp[amount];
+    }
+};
+```
