算法--动态规划

动态规划的本质是递归加缓存

解决动态规划的四个步骤:

  • 设计暴力算法,找到冗余
  • 设计并存储状态(一维,二维,三维数组,甚至用Map)
  • 递归式(状态转移方程)
  • 自底向上计算最优解(编程方式:把递归改为迭代)

(递归是自顶向下,循环是自底向上)
Leetcode198题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 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 。

从题目中可以看出,不能投相同的两间屋子,首先用DFS解决。下图中,根结点是0,表示从0号开始,决定偷还是不偷,如果决定偷0,那么1不能偷,只能偷2;如果不偷0,那么可以偷1.
imagepng

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int rob(int[] nums) {
return dfs(0,nums);
}
public int dfs(int idex, int[] nums) {
if(idex >= nums.length) {
return 0;
}
int a = nums[idex] + dfs(idex + 2, nums); //从左边开始
int b = 0 + dfs(idex + 1, nums); //从右边开始
return Math.max(a,b);
}
}

上面的代码可以解决问题,但是超出了时间限制,看上面的图,(2,n)和(3,n)出现了多次,所以在这个程序中有些结点计算了多次,那么可以使用缓存来保存这些节点,在需要的时候取出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
Map<Integer,Integer> cache = new HashMap<Integer,Integer>();
public int rob(int[] nums) {
return dfs(0,nums);
}
public int dfs(int idx, int[] nums) {
if(idx >= nums.length) {
return 0;
}
//取之前先判断一下缓存中是否存在值
if(cache.containsKey(idx)) {
return cache.get(idx);
}
int a = nums[idx] + dfs(idx + 2, nums); //从左边开始
int b = 0 + dfs(idx + 1, nums); //从右边开始
int c = Math.max(a,b);
//将每次的值保存在缓存中
cache.put(idx,c);
return c;
}
}

递归调用会占用许多空间,下面改为迭代的方式,自底向上来解决问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
Map<Integer,Integer> cache = new HashMap<Integer,Integer>();
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
int n = nums.length;
cache.put(n - 1,nums[n - 1]); //最后一个保存进去
for(int i = n - 2; i >= 0; i--) {
int a = nums[i] + (cache.containsKey(i + 2) ? cache.get(i + 2) : 0); //从左边开始
int b = 0 + (cache.containsKey(i + 1) ? cache.get(i + 1) : 0); //从右边开始
cache.put(i,Math.max(a,b));
}

return cache.get(0);
}

}

也可以使用数组来替换map,这样可以更节省空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
int[] cache = new int[100];
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return nums[0];
}
int n = nums.length;
cache[n - 1] = nums[n - 1]; //最后一个保存进去
cache[n - 2] = Math.max(nums[n - 1],nums[n - 2]);
for(int i = n - 3; i >= 0; i--) {
cache[i] = Math.max(nums[i] + cache[i + 2],cache[i + 1]);
}
return cache[0];
}
}