灵神【基础算法精讲】视频的个人笔记。
动态规划核心
启发思路（跟子集型回溯一样）
视频例题
回溯三问：
- 当前操作？枚举第 i 个房子选或不选。
- 子问题？从前 i 个房子中的最高金额。
- 下一个子问题？
- 选：从前 i-2 个房子中的最高金额。
- 不选：从前 i-1 个房子中的最高金额。
递归
1
2
3
4
5
6
7
8
9
10
11
12
| int rob(vector<int>& nums) {
int n = nums.size();
function<int(int)> dfs = [&](int i) -> int {
if(i < 0) return 0;
return max(dfs(i - 1), dfs(i - 2) + nums[i]);
};
return dfs(n - 1);
}
|
记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> cache(n, -1);
function<int(int)> dfs = [&](int i) -> int {
if(i < 0)
return 0;
if(cache[i] != -1) return cache[i];
return cache[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]);
};
return dfs(n - 1);
}
};
|
递推
- 从记忆化搜索一比一翻译过来:
dp[i] = max(dp(i - 1), dp(i - 2) + nums[i]);
- 防止越界, dp[i]中的 i 全部+2:
dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 2, 0);
for (int i = 0; i < n; ++i) {
dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]);
}
return dp[n + 1];
}
};
|
空间优化
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int rob(vector<int> &nums) {
int f0 = 0, f1 = 0;
for (int x : nums) {
int new_f = max(f1, f0 + x);
f0 = f1;
f1 = new_f;
}
return f1;
}
};
|
课后作业
- 1 和 2 是边界，提前赋值。
- 楼梯有 3 阶时，有两种方法：
- 从 1 阶 爬 1 个台阶，到达 3 阶
- 从 2 阶 爬 2 个台阶，到达 3 阶
- 到达 1 阶有 1 种方法，到达 2 阶有 2 种方法，到达 3 阶楼梯有 1+2=3 种方法。
- 同理，楼梯有 i 阶
- 从 i - 1 阶爬 1 个台阶
- 从 i - 2 阶爬 2 个台阶
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 3, 0);
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
|
详细题解力扣
回溯三问：
- 当前操作？枚举第 i 层从
i - 1层来 或 从 i - 2层来，然后加上第 i 层的花费。
- 子问题？到达第 i 层台阶的最小花费。
- 下一个子问题？
- 到达
i - 1层的最小花费
- 到达
i - 2层的最小花费
顶部是第 n 层，取 n-1和 n-2的最小值，min(dp[n - 1], dp[n - 2])。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1, 0);
for (int i = 0; i < 2; ++i) {
dp[i] = cost[i];
}
for (int i = 2; i < n; ++i) {
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
}
return min(dp[n - 1], dp[n - 2]);
}
};
|
记忆化搜索
dfs得出长度为 i 的好字符串的方案数- 循环, 求出长度从
low到 high的总方案数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
const int MOD = 1e9 + 7;
vector<int> cache(high + 1, -1);
function<int(int)> dfs = [&] (int i) -> int {
if(i < 0) return 0;
if(i == 0) return 1;
if(cache[i] != -1) return cache[i];
return cache[i] = (dfs(i - zero) + dfs(i - one)) % MOD;
};
int ans = 0;
for (int i = low; i <= high; ++i) {
ans += dfs(i) % MOD;
ans %= MOD;
}
return ans;
}
};
|
递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
const int MOD = 1e9 + 7;
vector<int> dp(high + 1, 0);
dp[0] = 1;
for (int i = 1; i <= high; ++i) {
if(i >= zero) dp[i] += dp[i - zero];
if(i >= one) dp[i] += dp[i - one];
dp[i] %= MOD;
}
int ans = 0;
for (int i = low; i <= high; ++i) {
ans += dp[i] % MOD;
ans %= MOD;
}
return ans;
}
};
|
官方题解力扣
跟例题打家劫舍的区别
用打家劫舍的解法，算两次
- 第一次求
0 ~ n-2
- 第二次求
1 ~ n-1
- 最后求最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
function<int(int, int)> dpRange = [&] (int start, int end) -> int {
vector<int> dp(n + 2);
for (int i = start; i <= end; ++i) {
dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]);
}
return dp[end + 2];
};
return max(dpRange(0, n - 2), dpRange(1, n - 1));
}
};
|
