8000 ;1 · Ainevsia/Leetcode-Rust@2af9c98 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2af9c98

Browse files
AinevsiaAinevsia
committed
;1
1 parent 8ca6cf2 commit 2af9c98

File tree

12 files changed

+265
-0
lines changed

12 files changed

+265
-0
lines changed

‎notes/src/SUMMARY.md

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -139,4 +139,15 @@
139139
- [96.不同的二叉搜索树](./day41/lc96.md)
140140
- [day 42](./day42.md)
141141
- [416. 分割等和子集](./day42/lc416.md)
142+
- [day 43](./day43.md)
143+
- [1049. 最后一块石头的重量 II](./day43/lc1049.md)
144+
- [494. 目标和](./day43/lc494.md)
145+
- [474. 一和零](./day43/lc474.md)
146+
- [day 44](./day44.md)
147+
- [518. 零钱兑换 II](./day44/lc518.md)
148+
- [377. 组合总和 Ⅳ](./day44/lc377.md)
149+
- [day 45](./day45.md)
150+
- [70. 爬楼梯 （进阶）](./day45/lc70.md)
151+
- [322. 零钱兑换](./day45/lc322.md)
152+
- [279.完全平方数](./day45/lc279.md)
142153
- [remains](./remains.md)

‎notes/src/day43.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# 第九章 动态规划 part05
2+
● 1049. 最后一块石头的重量 II
3+
● 494. 目标和
4+
● 474.一和零
5+
6+
详细布置
7+
## 1049. 最后一块石头的重量 II
8+
9+
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
10+
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
11+
https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
12+
## 494. 目标和
13+
大家重点理解 递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。
14+
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
15+
https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
16+
17+
## 474.一和零
18+
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
19+
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
20+
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
21+
22+
23+

‎notes/src/day43/lc1049.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 1049. 最后一块石头的重量 II
2+
3+
```cpp
4+
class Solution {
5+
public:
6+
int lastStoneWeightII(vector<int>& nums) {
7+
int sum = 0;
8+
for (int i = 0; i < nums.size(); i ++ ) {
9+
sum += nums[i];
10+
}
11+
int target = sum >> 1;
12+
vector<int> dp (1+target,0);
13+
for (int i = 0; i < nums.size(); i ++ ) {
14+
for (int j = target; j >= nums[i]; j -- ) {
15+
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
16+
}
17+
}
18+
return sum - dp[target]*2;
19+
}
20+
};
21+
```

‎notes/src/day43/lc474.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# 474.一和零
2+
3+
```cpp
4+
class Solution {
5+
public:
6+
int findMaxForm(vector<string>& strs, int m, int n) {
7+
// dp[i][j] 表示子集中最多i个0和j个1的最大子集长度
8+
vector<vector<int>>dp(1+m,vector<int>(1+n,0));
9+
// x = count(s.begin(),s.end(),'0');
10+
// y = s.size() - x;
11+
// dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1)
12+
for (int u = 0; u < strs.size() ; u ++ ) {
13+
string s = strs[u];
14+
int x = count(s.begin(),s.end(),'0');
15+
int y = s.size() - x;
16+
for ( int i = m ; i >= x; i -- ) {
17+
for ( int j = n ; j >= y; j -- ) {
18+
dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1);
19+
}
20+
}
21+
}
22+
return dp[m][n];
23+
}
24+
};
25+
```
26+
27+
这个题很舒服，自己一下写过的

‎notes/src/day43/lc494.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# 494.目标和
2+
3+
一开始不会做，一种心的dp推导公式
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int findTargetSumWays(vector<int>& nums, int target) {
9+
int sum = 0;
10+
for (int i = 0; i < nums.size(); i ++ ) {
11+
sum += nums[i];
12+
}
13+
int left = (target + sum);
14+
if (left & 1) return 0;
15+
left = left >> 1;
16+
vector<int>dp(left+1);
17+
dp[0] = 1;
18+
// dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
19+
for ( int i = 0; i < nums.size() ; i ++ ) {
20+
for (int j = dp.size() - 1; j >= nums[i] ; j -- ) {
21+
dp[j] += dp[j-nums[i]];
22+
}
23+
}
24+
return dp[left];
25+
}
26+
};
27+
```

‎notes/src/day44.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 第九章 动态规划part06
2+
● 完全背包
3+
● 518. 零钱兑换 II
4+
● 377. 组合总和 Ⅳ
5+
6+
详细布置
7+
8+
力扣上没有纯粹的完全背包的题目，所以大家看本篇了解一下 完全背包的理论
9+
10+
后面的两道题目，都是完全背包的应用，做做感受一下
11+
12+
## 完全背包
13+
视频讲解：https://www.bilibili.com/video/BV1uK411o7c9
14+
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
15+
16+
## 518. 零钱兑换 II
17+
视频讲解：https://www.bilibili.com/video/BV1KM411k75j
18+
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
19+
20+
## 377. 组合总和 Ⅳ
21+
视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6
22+
https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html

‎notes/src/day44/lc377.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 377. 组合总和 Ⅳ
2+
3+
不会做，抄了随想录
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int combinationSum4(vector<int>& nums, int target) {
9+
// dp[i] 表示总和为i的元素组合的个数
10+
vector<unsigned int>dp(1+target);
11+
dp[0]=1;
12+
for(int j=0;j<=target;j++){
13+
for(int i=0;i<nums.size();i++){
14+
if(j>=nums[i])
15+
dp[j]+=dp[j-nums[i]];
16+
}
17+
}
18+
return dp[target];
19+
}
20+
};
21+
```

‎notes/src/day44/lc518.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 518. 零钱兑换 II
2+
3+
第一道完全背包的题目，抄了随想录
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int change(int amount, vector<int>& coins) {
9+
// dp[j]：凑成总金额j的货币组合数为dp[j]
10+
vector<int>dp(amount+1);
11+
dp[0]=1;
12+
// dp[j] += dp[j - coins[i]];
13+
for(int i = 0; i < coins.size(); i ++ ) {
14+
for (int j = coins[i]; j <= amount; j ++ ) { // 完全背包，需要重复计算之前的组合数
15+
dp[j] += dp[j-coins[i]];
16+
}
17+
}
18+
return dp[amount];
19+
}
20+
};
21+
```

‎notes/src/day45.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# 第九章 动态规划part07
2+
3+
● 70. 爬楼梯 （进阶）
4+
● 322. 零钱兑换
5+
● 279.完全平方数
6+
7+
详细布置
8+
9+
## 70. 爬楼梯 （进阶）
10+
11+
这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍
12+
13+
https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html
14+
15+
## 322. 零钱兑换
16+
17+
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
18+
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
19+
20+
这句话结合本题 大家要好好理解。
21+
视频讲解：https://www.bilibili.com/video/BV14K411R7yv
22+
https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
23+
24+
## 279.完全平方数
25+
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
26+
视频讲解：https://www.bilibili.com/video/BV12P411T7Br
27+
https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

‎notes/src/day45/lc279.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# 279.完全平方数
2+
3+
4+
喜喜这个自己做的
5+
```cpp
6+
class Solution {
7+
public:
8+
int numSquares(int n) {
9+
// dp[i] 和为 i 的完全平方数的最少数量
10+
// dp[j] = min(dp[j],dp[j-i*i]+1)
11+
vector<int>dp(1+n,INT_MAX);
12+
dp[0]=0;
13+
for(int i = 1; i * i <= n; i ++ ) {
14+
for(int j = i*i; j <= n; j ++ ) {
15+
dp[j] = min(dp[j],dp[j-i*i]+1);
16+
}
17+
}
18+
return dp[n];
19+
}
20+
};
21+
```

0 commit comments

Comments
 (0)
0