剑客
关注科技互联网

我对于动态规划的理解

动态规划很早就接触过了,但一直都心存疑惑。网上的一些文章,基本都是满篇术语。 状态转移
状态方程
,这种名词,其实是让初学者比较迷惑。直到我上完 Berkeley
CS 61 A
, 突然就理解了所谓的动态规划。或者说是真正的理解了递归。把玩函数式语言对理解递归,或者说程序结构,非常有帮助。 SICP
这本书已经很多人推荐了,用 Scheme
讲的,我没看完,看了大概前面两章。我比较推荐的是 华盛顿大学
Programming Languages
还有上面 Berkeley
那门课。

动态规划

我认为所谓的动态规划,就是递归的记忆化过程。这里必须要提一个函数式语言的好处,支持 尾递归
尾递归
可以用来防止重复计算。可惜很多语言并不支持,很容易就栈溢出了,比如 JAVA
Python
。所以需要把递归改写成循环形式。其实本质还是和尾递归一样。都是拿空间换时间。

斐波那契

首先我门先写一个递归版的斐波那契。

public static int fib(int n){
if (n == 1 || n == 2)
return 1;
else return fib(n -1) + fib(n -2);
}

这个函数有大量的重复计算。是个树形结构。比如计算 fib(10)
,那么他会分别计算 fib(9)
, fib(8)
,当计算 fib(9)
时,会计算 fib(8)
, fib(7)
, fib(6)
…但是当计算 fib(8)
时,上面的计算过程又要重复一遍。

我测试了一下 fib(50)
,已经要等很久才出结果了。

接下来我们改写它。把计算的过程储存起来。也就是 记忆化

变形一

public static final int N = 100;
public static double[] fibs = new double[N];
public static double fib(int n){
if (n == 1 || n == 2)
return 1;
else if (fibs[n] != 0) return fibs[n];
else return fibs[n] = fib(n -1) + fib(n -2);
}

很简单。多开了个数组来保存已经计算过的值。节省大量重复的计算。 fib(50)
可以秒算。这其实就是一个动态规划的过程。注意这里有两个比较动态规划比较重要的特性。也就是 重叠子问题
最优子结构
。比如说斐波那契的每一个数,都是依靠前面两个数的和计算得出,也就是 最优子结构
。但如果不记忆化,就会有大量重复计算,这就是 重叠子问题

接下来我们再来看一个尾递归版,但是注意 JAVA
并不支持尾递归,容易栈溢出。这里只做演示。

变形二

static double fib_tail(int n, double a, double b) {
if (n == 1 || n == 2) {
return b;
} else {
return fib_tail(n - 1, b, a + b);
}
}

通过把计算结果保存到参数中,来简化计算结果。其实原理和上面开数组是一样的。也可以秒算 fib_tail(50,1,1)

变形三

第三种方法直接用循环来做。既节省递归切换的时间,又避免了尾递归栈溢出的烦恼。

public static double fib3(int n) {
double a = 0;
double b = 1;
double c;
for (int i = 1; i < n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}

其实就是这么简单。下面看一个略复杂的。

House Robber

House Robber
。大概意思就是给你个数组,挑一串数字使和最大化,但每两个数不能相邻。

public class Solution { 
private int[] robs;
public int rob(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
robs = new int[nums.length];
Arrays.fill(robs,-1);
return rob(nums,0);
}

private int rob(int[] nums, int i){
if (i >= nums.length) return 0;
if (robs[i] != -1) return robs[i];
int max = Integer.max(rob(nums,i+1),nums[i] + rob(nums,i+2));
return robs[i] = max;
}
}

这是我的版本。我更喜欢用递归来描述问题。思路是数组里的每一数,我有两种选择,选或者不选,选了这个就不能选下一个,递归的求解,然后进行比较,选取较大的大个,并且用数组记忆结果。这就是所谓带备忘的 自顶向下法

再给出一种方法,我在 LeetCode
论坛找的。

public int rob(int[] nums) {  
if(nums.length==0) return 0;
if(nums.length==1) return nums[0];

//Initialize an arrays to store the money
int[] mark = new int[nums.length];

//We can infer the formula from problem:mark[i]=max(num[i]+mark[i-2],mark[i-1])
//so initialize two nums at first.
mark[0] = nums[0];
mark[1] = Math.max(nums[0], nums[1]);

//Using Dynamic Programming to mark the max money in loop.
for(int i=2;i<nums.length;i++){
mark[i] = Math.max(nums[i]+mark[i-2], mark[i-1]);
}
return mark[nums.length-1];
}

这里注释很清楚,不多做解释。这种方法也就是所谓的 自底向下法
,不需要递归切换,速度会比上面那种快。

最后

当然,如果你需要熟练掌握动态规划,必须进行大量的练习。

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址