动态规划定义
- 本质：递归
- 原问题(N) -> 子问题(N-1) ->原问题(N)
- 最优子结构
- 子问题最优决策可导出原问题最优决策
- 无后效性
重叠子问题
套路关键词
- 最优、最大、最小、最长、计数
- 离散问题
- 容易设计状态（整数01背包问题）
最优子结构
四个步骤
- 设计暴力算法，找到冗余
- 设计并存储状态（一维、二维、三维数组，甚至用Map）
- 递归式（状态转移方程）
- 自底向上计算最优解（编程方式）
总结
- 动态规划算法用到的题目存在很多套路
- 滚动数组，状态压缩，升维，单调性，四边形不等式（高级套路）
- 先学套路、跳出套路
- 先暴力、找冗余、去冗余
LeetCode 198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解析：
本题等同于在一个数组中取出一些数字，这些数字不可以是相邻的，怎么取使得最终这些数字的和最大
- 暴力法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution{
public int solve(int idx,int[] nums){
if(idx < 0){
return 0;
}
return Math.max(nums[idx] + solve(idx - 2 , nums),
solve(idx - 1 , nums));
}
public int rob(int[] nums){
return solve(nums.length - 1 , nums);
}
}
分析：
- 时间复杂度：O(2^n)
利用暴力法会重复计算许多已经算出来的结果
如果第一次抢n-1 , 那么他可以抢 n-3,n-4,n-5,…
如果第一次抢n-2,那么他可以抢n-4,n-5,…
由此可见1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution{
public int solve(int idx,int[] nums){
if(idx < 0){
return 0;
}
if(idx 算过){
直接返回
}
return Math.max(nums[idx] + solve(idx - 2 , nums),
solve(idx - 1 , nums));
}
public int rob(int[] nums){
return solve(nums.length - 1 , nums);
}
}
可以利用一个一维数组来保存每次计算的值，之后用到的时候直接返回，这时利用空间换时间
1 | class Solution { |
时间复杂度：O(n),那能不能不用递归呢?1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public class Solution2 {
public int[] result;
public int rob(int[] nums) {
if(nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
result = new int[nums.length];
result[0] = nums[0];
result[1] = Math.max(nums[0], nums[1]);
for(int i = 2 ; i < nums.length ; i++){
result[i] = Math.max(nums[i] + result[i - 2],
result[i - 1]);
}
return result[nums.length - 1];
}
}
