题目来源
题目描述
class Solution {
public:
int rob(vector<int>& nums) {
}
};
题目解析
-
动态规划的本质是递归，递归解决不了的问题，动态规划也解决不了
-
所有的算法都是穷举，只是是不是聪明的穷举
暴力搜索
class Solution {
/*
* 从第一家开始抢(也可以从第一家最后一家开始抢，习惯性缩小问题的规模)
* idx：表示抢到了第几家店
* */
int process(int idx, std::vector<int> & nums){
int N = nums.size();
if(idx == N){
return 0;
}
if(idx == N - 1){
return nums[idx];
}
/* 对于当前店，我们有两种决策
* * 抢： 得到了收益 nums[idx]， 但是不能抢下一家店了
* * 不抢：可以抢下一家点
* 从这两种决策中选一种最大的
* */
int p1 = process(idx + 1, nums);
int p2 = nums[idx] + process(idx + 2, nums);
return std::max(p1, p2);
}
public:
int rob(vector<int>& nums) {
return process(0, nums);
}
};
-
时间复杂度分析：
- 对于每一家店，有两种决策（每个点只抢一家店），一共有N个店，那么时间复杂度是2^N
- 它会超时，优化一定是去掉冗余，用数组、map之类的存储
另外：
- 暴力搜索一定是递归，不可能是迭代。
- 暴力递归本质上是枚举，但是用迭代的话代码就太难写了，所以一般写成递归
思路
-
假设当前来到了i，那么i有两种可能性：
- 抢
- 不抢
-
如果抢，它会影响
i+
1
i + 1
i
+
1
，但是不会影响
ii
i
之前的状态 -
所以我们假定
[0…
i
−
1
]
[0…i-1]
[
0…
i
−
1
]
都被解决了。 -
问题是
ii
i
能不能抢呢？因为
[0…
i
−
1
]
[0…i-1]
[
0…
i
−
1
]
不会影响
ii
i
，所以它可以自由选择抢还是不抢。只是这个抢还是不抢会影响
i+
1
i+1
i
+
1
而已
记忆化搜索（记忆化搜索可以看出是动态规划）
为什么要上备忘录
因为这道题所有数都是整数，所以要尽可能的抢，才能得到最佳效率
- 假设当前抢了n –> 那么下一家可能是（n + 2，n + 3，n + 4…）
- 假设当前抢了n –> 那么下一家可能是（n + 3，n + 4…）
- …
从上面，可以看出会大量重复计算，也就是n + 3，n + 4…
为什么这道题不能用贪心算法解决。
-
因为这道题有后滞性。
- 我们抢了第n家店，那么第n+1家店就不能抢了
- 所以只能dp，不能贪心（贪心问题必须天生无后效性）
-
dp是怎么处理后效性的？（dp的本质是递归，递归不能解决的问题dp一定不能解决）
-
后效性就是：
- 当抢了第n家店，那么第n+1家店就不能抢了
-
也就是说做了当前
决策
之后，会影响后面的
决策
- 没有做当前决策之前，每家店都能抢
- 做了当前决策之后，不是每家店都能抢了
-
从上面递归代码可以看出
-
当抢了
nums[idx]
，下一个问题就缩小为
solve(idx + 2, nums)
，跳过了
idx + 1
—->
nums[idx] + solve(idx + 2, nums)
—> 也就是说，将[后效性]处理成了[无后效性] -
当不抢
nums[idx]
时，本来就[无后效性]，所以问题缩小为
solve(idx + 1, nums)
-
当抢了
-
后效性就是：
两个概念
-
最优子结构
- 子问题最优决策可以导出原问题最优决策
- 无后效性：如果原问题有后效性，应该将之改造成无后效性
-
重叠子问题
- 需要解决重叠子问题，也就是说去冗余：
- 一般方法是：空间换时间
-
套路：
- 题目中出现“最优、最大、最小、最长、计数”之类的
-
动态规划一般都是离散问题
- 比如背包重量都是整数时，就是01背包；如果背包是小数，那么就悬
- 为什么必须是离散：因为小数不容易穷举和存储
代码
class Solution {
std::vector<int> result;
int process(int idx, std::vector<int> & nums){
int N = nums.size();
if(idx == N){
return 0;
}
if(idx == N - 1){
return nums[idx];
}
if(result[idx] >= 0){ // 不是初始化状态，说明一定处理过了
return result[idx];
}
result[idx] = std::max(
process(idx + 1, nums),
nums[idx] + process(idx + 2, nums)
);
return result[idx];
}
public:
int rob(vector<int>& nums) {
result.resize(nums.size());
for (int i = 0; i < result.size(); ++i) {
result[i] = -1; // 因为要求最大值
}
return process(0, nums);
}
};
这就是dp，也叫做记忆化搜索。
- 时间复杂度： O[N]（每家店只计算一次）
- 空间复杂度：O[N]
序列型动态规划
思路一：将记忆化搜索改为动态规划
class Solution {
std::vector<int> result;
public:
int rob(vector<int>& nums) {
if(nums.empty()){
return 0;
}
if(nums.size() == 1){
return nums[0];
}
result.resize(nums.size());
for (int i = 0; i < result.size(); ++i) {
result[i] = -1; // 因为要求最大值
}
result[0] = nums[0]; // 只有一家店，那就只能强这一家了
result[1] = std::max(nums[0], nums[1]); // 有两家店，那就抢钱多的那一家
for (int idx = 2; idx < nums.size(); ++idx) {
result[idx] = std::max(
nums[idx] + result[idx - 2],
result[idx - 1]
);
}
return result[nums.size() - 1];
}
};
思路二：将暴力递归改为动态规划
（1）第一步：准备一张表
- 问题是，这张表是一维的还是二维的，应该多大。我们可以通过分析递归函数的可变参数有几个，其变化范围多大来决定
int process(int idx, std::vector<int> & nums)
-
可变参数为：idx，其变化范围是
0~N
- 因为只有一个可变参数，所以dp应该是一维数组；因为变化范围是0~n，所以数组长度为n+1。也就是：
std::vector<int> dp(n + 1)
（2）确定返回值
- 怎么确定呢？通过看主函数是怎么调用递归函数的
return process(0, nums);
-
可以看出，可变参数初始为0，所以应该返回
dp[0]
（3）填表
（3.1）先初始化表，也就是看base case
int N = nums.size();
if(idx == N){
return 0;
}
if(idx == N - 1){
return nums[idx];
}
-
因此初始化：
dp
[
n
]
=
0
，
d
p
[
n
−
1
]
=
n
u
m
s
[
i
d
x
]
dp[n] = 0，dp[n – 1] = nums[idx]
d
p
[
n
]
=
0
，
d
p
[
n
−
1
]
=
n
u
m
s
[
i
d
x
]
（3.2） 再分析普通情况，这个时候要分析清楚依赖关系
int p1 = process(idx + 1, nums);
int p2 = nums[idx] + process(idx + 2, nums);
return std::max(p1, p2);
- 可以看出，它主要依赖右边两个表格的值，因此，应该从右往左填写
for (int idx = n - 2; idx >= 0; --idx) {
}
- 置于怎么填，照着上面依赖关系抄就行了
综上：
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.empty()){
return 0;
}
int n = nums.size();
std::vector<int> dp(n + 1);
dp[n] = 0;
dp[n - 1] = nums[n - 1];
for (int idx = n - 2; idx >= 0; --idx) {
int p1 = dp[idx + 1];
int p2 = dp[idx + 2] + nums[idx];
dp[idx] = std::max(p1, p2);
}
return dp[0];
}
};
美团面试题：
题目描述
给定一个数组arr，在不能取相邻数的情况下，返回所有组合中的最大累加和
题目解析
就是
打家劫舍
，代码是一样的
定义： dp[i]为[0…i]范围上不相邻的情况下，怎么选取能够得到最大累加和
思路
思考：0~i范围上得到的最好累加和的可能性有哪些？
- 只要这个数时，累加和最大
-
不要这个数时，累加和最大
-
因为不要这个数
ar
r
[
i
]
arr[i]
a
rr
[
i
]
，
[0
，
i
−
1
]
[0，i-1]
[
0
，
i
−
1
]
范围上怎么选那么就选择选
-
因为不要这个数
-
既要这个数，也要左边的数时，累加和最大
-
因为要这个数
ar
r
[
i
]
arr[i]
a
rr
[
i
]
，那么相邻的
ar
r
[
i
−
1
]
arr[i-1]
a
rr
[
i
−
1
]
就不能选，左边只能在
[0
，
i
−
2
]
[0，i-2]
[
0
，
i
−
2
]
范围上选择
-
因为要这个数
特殊情况：
- 当只有一个数时
- 当只有两个数时
返回值：dp[N-1]：表示在[0…N-1]范围上不相邻的情况下，怎么选取能够得到最大累加和
int rob(std::vector<int>& nums){
if(nums.empty() ){
return 0;
}
int N = nums.size();
if(N == 1){
return nums[0];
}
if(N == 2){
return std::max(nums[0], nums[1]);
}
std::vector<int> dp(N);
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for (int i = 2; i < N; ++i) {
dp[i] = std::max(nums[i], std::max(dp[i - 1], nums[i] + dp[i - 2]));
}
return dp[N-1];
}
类似题目