Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit194abf8

Browse files
Update
1 parentf53e2b2 commit194abf8

10 files changed

+161
-67
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,6 +218,9 @@
218218
*[本周小结！（贪心算法系列三）](https://mp.weixin.qq.com/s/JfeuK6KgmifscXdpEyIm-g)
219219
*[贪心算法：根据身高重建队列（续集）](https://mp.weixin.qq.com/s/K-pRN0lzR-iZhoi-1FgbSQ)
220220
*[贪心算法：用最少数量的箭引爆气球](https://mp.weixin.qq.com/s/HxVAJ6INMfNKiGwI88-RFw)
221+
*[贪心算法：无重叠区间](https://mp.weixin.qq.com/s/oFOEoW-13Bm4mik-aqAOmw)
222+
*[贪心算法：划分字母区间](https://mp.weixin.qq.com/s/pdX4JwV1AOpc_m90EcO2Hw)
223+
*[贪心算法：合并区间](https://mp.weixin.qq.com/s/royhzEM5tOkUFwUGrNStpw)
221224

222225

223226
* 动态规划

‎problems/0070.爬楼梯.md

Lines changed: 18 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -25,30 +25,40 @@ public:
2525

2626
既然这么简单为什么还要讲呢，其实本题稍加改动就是一道面试好题，如果每次可以爬 1 或 2或3或者m 个台阶呢，走到楼顶有几种方法？
2727

28-
29-
3028
* 确定dp数组以及下标的含义
3129

3230
dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法
3331

3432
* 确定递推公式
3533

36-
dp[i]有几种来源，dp[i - 1]，dp[i - 2]
34+
dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]
35+
36+
那么递推公式为：dp[i] += dp[i - j]
3737

3838
* dp数组如何初始化
39+
40+
既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
41+
42+
下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
43+
3944
* 确定遍历顺序
4045

41-
dp里求排列，1 2 步 和 2 1 步都是上三个台阶，但不一样！
46+
这是背包里求排列问题，即：1 2 步 和 2 1 步都是上三个台阶，但是这两种方法不！
4247

43-
这是求排列
48+
所以需将target放在外循环，将nums放在内循环。
49+
50+
每一步可以走多次，说明这是完全背包，内循环需要从前向后遍历。
51+
52+
53+
C++代码如下：
4454
```
4555
class Solution {
4656
public:
4757
int climbStairs(int n) {
4858
vector<int> dp(n + 1, 0);
4959
dp[0] = 1;
5060
for (int i = 1; i <= n; i++) {
51-
for (int j = 1; j <=2; j++) {
61+
for (int j = 1; j <=m; j++) {
5262
if (i - j >= 0) dp[i] += dp[i - j];
5363
}
5464
}
@@ -57,6 +67,8 @@ public:
5767
};
5868
```
5969

70+
代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯的代码了。
71+
6072
#总结
6173

6274
如果我来面试的话，我就会想给候选人出一个 本题原题，看其表现，如果顺利写出来，进而在要求每次可以爬[1 - m]个台阶应该怎么写。

‎problems/0139.单词拆分.md

Lines changed: 34 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,4 @@
11

2-
// 如何往 完全背包上靠？
3-
// 用多次倒是可以往 完全背包上靠一靠
4-
// 和单词分割的问题有点像
5-
62
[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)
73

84
回溯法代码：
@@ -68,11 +64,40 @@ public:
6864
};
6965
```
7066

67+
#背包
7168

72-
得好好分析一下，完全背包和01背包，这个对于刷leetcode太重要了
69+
* 确定dp数组以及下标的含义
7370

74-
注意这里要空出一个 dp[0] 来做起始位置
75-
```
71+
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词
72+
73+
* 确定递推公式
74+
75+
如果确定dp[j] 是true，且[j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）
76+
77+
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j] ==true) 那么 dp[i] = true
78+
79+
80+
* dp数组如何初始化
81+
82+
从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了。
83+
84+
同时也表示如果字符串为空的话，说明出现在字典里。
85+
86+
下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
87+
88+
* 确定遍历顺序
89+
90+
题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。
91+
92+
同时也说明出现的单词集合是组合还是排列，并不在意，最终要求的是 是否都出现过。
93+
94+
所以本题使用求排列的方式，还是求组合的方式都可以。
95+
96+
我采用的求排列的方式，所以遍历顺序：target放在外循环，将nums放在内循环。内循环从前到后。
97+
98+
C++代码如下：
99+
100+
```C++
76101
classSolution {
77102
public:
78103
bool wordBreak(string s, vector<string>& wordDict) {
@@ -93,4 +118,5 @@ public:
93118
}
94119
};
95120
```
96-
时间复杂度起始是O(n^3)，因为substr返回子串的副本是O(n)的复杂度（n是substring的长度）
121+
* 时间复杂度：O(n^3)，因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）
122+
* 空间复杂度：O(n)

‎problems/0279.完全平方数.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
11
没有问你组合方式，而是问你最小个数
22

3+
和322 一个套路
4+
35
// 组合的逻辑
46
```
7+
// 版本一
58
class Solution {
69
public:
710
int numSquares(int n) {
@@ -23,9 +26,31 @@ public:
2326
};
2427
```
2528

29+
优化一下代码，可以不用预先用sum数组来装i * i，但是版本一更清晰一些，代码如下：
30+
```
31+
// 版本二
32+
class Solution {
33+
public:
34+
int numSquares(int n) {
35+
vector<int> dp(n + 1, INT_MAX);
36+
dp[0] = 0;
37+
for (int i = 1; i * i <= n; i++) {
38+
for (int j = 1; j <= n; j++) {
39+
if (j - i * i >= 0 && dp[j - i * i ] != INT_MAX) {
40+
dp[j] = min(dp[j - i * i ] + 1, dp[j]);
41+
}
42+
}
43+
}
44+
return dp[n];
45+
}
46+
};
47+
48+
```
49+
2650

2751
// 排列的逻辑
2852
```
53+
// 版本三
2954
class Solution {
3055
public:
3156
int numSquares(int n) {

‎problems/0322.零钱兑换.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,13 +5,13 @@ dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
55

66
* 确定递推公式
77

8-
得到dp[j]（有考虑coins[i]），有两个来源，一个是dp[j - coins[i]]，一个是dp[j]（没有考虑coins[i]）自己。
8+
得到dp[j]（考虑coins[i]），只有一个来源，dp[j - coins[i]]（没有考虑coins[i]）。
99

1010
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
1111

12-
所以dp[j]（有考虑coins[i]）有两个选择，dp[j]（没有考虑coins[i]）和dp[j - coins[i]] + 1（考虑coins[i]），一定是取最小的。
12+
所以dp[j] 要去所有dp[j - coins[i]] + 1 中最小的。
1313

14-
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
14+
递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
1515

1616
* dp数组如何初始化
1717

‎problems/0377.组合总和Ⅳ.md

Lines changed: 39 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,41 @@
1+
#思路
12

2-
和之前个回溯法的各个总和串起来一波，本题用回溯稳稳的超时
3+
本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！
4+
5+
弄清什么是组合，什么是排列很重要。
6+
7+
大家在学习回溯算法系列的时候，一定做过这两道题目[回溯算法：39.组合总和](https://mp.weixin.qq.com/s/FLg8G6EjVcxBjwCbzpACPw)和[回溯算法：40.组合总和II](https://mp.weixin.qq.com/s/_1zPYk70NvHsdY8UWVGXmQ)
8+
9+
大家会感觉很像，但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。
10+
11+
如果本题要把排列都列出来的话，只能使用回溯算法爆搜。
12+
13+
14+
* 确定dp数组以及下标的含义
15+
16+
dp[i]: 凑成目标正整数为i的组合个数为dp[i]
17+
18+
* 确定递推公式
19+
20+
dp[i]（考虑nums[j]）可以由 dp[i - nums[j]]（不考虑nums[j]） 推导出来。
21+
22+
因为只要得到nums[j]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。
23+
24+
所以递归公式: dp[i] += dp[i - nums[j]];
25+
26+
* dp数组如何初始化
27+
28+
因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
29+
30+
非0下标的dp[i]初始化为0，这样才不会影响dp[i]累加所有的dp[i-nums[j]]
31+
32+
* 确定遍历顺序
33+
34+
个数可以不限使用，这是一个完全背包，且得到的集合是排列（需要考虑元素之间的顺序）。
35+
36+
所以将target放在外循环，将nums放在内循环，内循环从前到后遍历。
37+
38+
C++代码如下：
339

440
```
541
class Solution {
@@ -19,28 +55,9 @@ public:
1955
};
2056
```
2157

58+
C++测试用例有超过两个树相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
2259

23-
C++测试用例有超过两个树相加超过int的数据
24-
超限的情况
60+
但java就不用考虑这个限制，我理解java里的int也是四个字节吧，也有可能leetcode后台对不同语言的测试数据不一样。
2561

2662

27-
一些题解会直接用ull usigned long long
2863

29-
java 也是四个字节，理论上没有差别，可能后台java和C++测试用例不同，bug.....
30-
```
31-
class Solution {
32-
public:
33-
int combinationSum4(vector<int>& nums, int target) {
34-
vector<int> dp(target + 1, 0);
35-
dp[0] = 1;
36-
for (int i = 0; i <= target; i++) {
37-
for (int num : nums) {
38-
if (i - num >= 0 && dp[i] < INT_MAX - dp[i - num]) {
39-
dp[i] += dp[i - num];
40-
}
41-
}
42-
}
43-
return dp[target];
44-
}
45-
};
46-
```

‎problems/0435.无重叠区间.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -157,7 +157,7 @@ public:
157157
};
158158
```
159159

160-
这里按照作弊案件遍历，或者按照右边界遍历，都可以AC，具体原因我还没有仔细看，后面有空再补充。
160+
这里按照左区间遍历，或者按照右边界遍历，都可以AC，具体原因我还没有仔细看，后面有空再补充。
161161
```C++
162162
classSolution {
163163
public:

‎problems/0474.一和零.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,9 @@
88
搞不懂 leetcode后台是什么牛逼的编译器，初始化int dp[101][101] = {0}; 可以 ，int dp[101][101];就不行，有其他默认值，坑死。
99
代码我做了实验，后台会拿findMaxForm，运行两次，取第二次的结果，dp有上次记录的数值。
1010

11+
本题其实不是多重背包问题，还是一个01背包问题，m 和 n 可以理解是一个二维的背包，而不同长度的字符串就是不同大小的待装物品。
12+
13+
1114
```
1215
class Solution {
1316
public:

‎problems/0518.零钱兑换II.md

Lines changed: 32 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,43 @@
11

2-
// 计算有多少种方式
3-
// 完全背包 for循环的顺序啊，先是哪个for 后是哪个for定不下来
2+
#思路
43

5-
排列
6-
```
7-
class Solution {
8-
public:
9-
int change(int amount, vector<int>& coins) {
10-
int dp[50001] = {0};
11-
dp[0] = 1;
12-
for (int i = 0; i <= amount; i++) {
13-
for (int j = 0; j < coins.size(); j++) { // 这是组合把？？？
14-
if (i - coins[j] >= 0) dp[i] += dp[i - coins[j]];
15-
}
16-
for (int j = 0; j <= amount; j++) {
17-
cout << dp[j] << " ";
18-
}
19-
cout << endl;
20-
}
21-
return dp[amount];
22-
}
23-
};
24-
```
4+
这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包
5+
6+
那么用动规四步曲来进行分析：
7+
8+
* 确定dp数组以及下标的含义
9+
10+
dp[j]：凑成总金额j的货币组合数为dp[j]
11+
12+
* 确定递推公式
13+
14+
dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
15+
16+
所以递推公式：dp[j] += dp[j - coins[i]];
17+
18+
* dp数组如何初始化
19+
20+
首先dp[0]一定要为1，dp[0]=1是 递归公式的基础。
21+
22+
下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
23+
24+
* 确定遍历顺序
25+
26+
本题是完全背包，而且求的是组合，不涉及钱币的顺序
27+
28+
所以 nums放在外循环，target在内循环，内循环正序遍历。
29+
30+
C++代码如下：
2531

26-
这个才是组合，本题的题解，
2732
```
2833
class Solution {
2934
public:
3035
int change(int amount, vector<int>& coins) {
31-
int dp[50001] = {0};
36+
vector<int> dp(amount + 1, 0);
3237
dp[0] = 1;
33-
for (int i = 0; i < coins.size(); i++) { // 一个钱币只在序列里出现一次
34-
for (int j =0; j <= amount; j++) {
35-
if (j - coins[i] >= 0)dp[j] += dp[j - coins[i]];
38+
for (int i = 0; i < coins.size(); i++) {
39+
for (int j =coins[i]; j <= amount; j++) {
40+
dp[j] += dp[j - coins[i]];
3641
}
3742
}
3843
return dp[amount];

‎problems/背包问题理论基础.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,9 @@
2424

2525
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略 微一改即可。
2626

27+
与 0-1 背包的区别在于每种物品 y 有 k 个，而非 1 个
28+
29+
力扣上面没有多重背包的题目。
2730
#总结
2831

2932
<imgsrc='../pics/416.分割等和子集1.png'width=600> </img></div>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp