网络科技

    今日:353| 主题:244809
收藏本版
互联网、科技极客的综合动态。

[其他] 我对于动态规划的理解

[复制链接]
男的也很單純 发表于 2016-10-12 16:26:38
167 7

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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

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

  首先我门先写一个递归版的斐波那契。
           
  1. 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),已经要等很久才出结果了。  
  接下来我们改写它。把计算的过程储存起来。也就是    记忆化。  
  变形一  

           
  1. 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并不支持尾递归,容易栈溢出。这里只做演示。  
  变形二  

           
  1. 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)。  
  变形三  

  第三种方法直接用循环来做。既节省递归切换的时间,又避免了尾递归栈溢出的烦恼。
           
  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。大概意思就是给你个数组,挑一串数字使和最大化,但每两个数不能相邻。  
           
  1. 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论坛找的。  
           
  1. 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];}
复制代码
       这里注释很清楚,不多做解释。这种方法也就是所谓的    自底向下法,不需要递归切换,速度会比上面那种快。  
  最后  

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




上一篇:Amazon undercuts Spotify and Apple Music with $7.99 streaming for Prime members
下一篇:Why the top entrepreneurs are seeking corporate venture money
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

哟西 发表于 2016-10-12 18:34:27
为了楼主,我拼了,楼下的抱紧大腿。。。
回复 支持 反对

使用道具 举报

刘小川 发表于 2016-10-12 19:35:14
您忘记吃药了吧?
回复 支持 反对

使用道具 举报

以柳 发表于 2016-10-13 05:04:02
大家不要急,排队来顶贴!
回复 支持 反对

使用道具 举报

旧时光她是个美人 发表于 2016-10-22 04:59:33
作为失败的典型,你实在是太成功了。
回复 支持 反对

使用道具 举报

董秀 发表于 2016-10-22 04:59:58
大人,此事必有蹊跷!
回复 支持 反对

使用道具 举报

撒发 发表于 2016-11-14 06:16:01
我就是来看帖子的,楼主英明啊!
回复 支持 反对

使用道具 举报

冯敏 发表于 2016-11-16 10:57:02
走过路过,千万不要错过!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表