动态规划算法

动态规划的关键点：

1. 最优化原理，也就是最优子结构性质。这指的是一个最优化策略具有这样的性质，无论过去状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略，简单来说就是一个最优化策略的子策略总是最优的，如果一个问题满足最优化原理，就称其有最优子结构性质。
2. 无后效性，指的是某个状态下的决策的收益，只与状态和决策相关，与达到该状态的方式无关。
3. 子问题的重叠性，动态规划将原来指数级的暴力搜索算法改进到了具有多项式时间复杂度的算法，其中的关键在于解决了冗余、重复计算的问题，这是动态规划算法的根本目的。
4. 总体来说，动态规划算法就是一系列以空间换取时间的算法。

动态规划使用

下面通过递归方式计算问题斐波那契数列（Fibonacci sequence）来阐述分治法不是银弹。

斐波那契数列指的是这样一个数列 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

自然中的斐波那契数列
斐波那契数列数学表示

这个数列从第3项开始，每一项都等于前两项之和。
下面给出递归实现的代码：

    /**
     * 求解Fibonacci数列中第n个元素的值
     * @param n 斐波那契数列中的位置
     * @return Fibonacci数列中第n个元素的值
     */
    public int fibonacci(int n) {
        if(n<2) return n;
        if(n>=2) {
            return fibonacci(n-1)+fibonacci(n-2);
        }
        return -1;
    }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0                计算用时        0ms
fibonacci 1 is 1                计算用时        1ms
fibonacci 2 is 1                计算用时        0ms
fibonacci 3 is 2                计算用时        0ms
fibonacci 4 is 3                计算用时        0ms
fibonacci 5 is 5                计算用时        0ms
fibonacci 6 is 8                计算用时        0ms
fibonacci 7 is 13               计算用时        0ms
fibonacci 8 is 21               计算用时        0ms
fibonacci 9 is 34               计算用时        0ms
fibonacci 10 is 55              计算用时        0ms
fibonacci 11 is 89              计算用时        0ms
fibonacci 12 is 144             计算用时        0ms
fibonacci 13 is 233             计算用时        0ms
fibonacci 14 is 377             计算用时        0ms
fibonacci 15 is 610             计算用时        0ms
fibonacci 16 is 987             计算用时        0ms
fibonacci 17 is 1597            计算用时        1ms
fibonacci 18 is 2584            计算用时        0ms
fibonacci 19 is 4181            计算用时        0ms
fibonacci 20 is 6765            计算用时        0ms
fibonacci 21 is 10946           计算用时        0ms
fibonacci 22 is 17711           计算用时        0ms
fibonacci 23 is 28657           计算用时        1ms
fibonacci 24 is 46368           计算用时        0ms
fibonacci 25 is 75025           计算用时        1ms
fibonacci 26 is 121393          计算用时        1ms
fibonacci 27 is 196418          计算用时        1ms
fibonacci 28 is 317811          计算用时        3ms
fibonacci 29 is 514229          计算用时        2ms
fibonacci 30 is 832040          计算用时        4ms
fibonacci 31 is 1346269         计算用时        8ms
fibonacci 32 is 2178309         计算用时        11ms
fibonacci 33 is 3524578         计算用时        20ms
fibonacci 34 is 5702887         计算用时        29ms
fibonacci 35 is 9227465         计算用时        46ms
fibonacci 36 is 14930352        计算用时        73ms
fibonacci 37 is 24157817        计算用时        127ms
fibonacci 38 is 39088169        计算用时        186ms
fibonacci 39 is 63245986        计算用时        306ms
fibonacci 40 is 102334155       计算用时        505ms
fibonacci 41 is 165580141       计算用时        816ms
fibonacci 42 is 267914296       计算用时        1298ms
fibonacci 43 is 433494437       计算用时        2110ms
fibonacci 44 is 701408733       计算用时        3423ms
fibonacci 45 is 1134903170      计算用时        5525ms
fibonacci 46 is 1836311903      计算用时        9013ms
fibonacci 47 is -1323752223     计算用时        14382ms

可以看出，n=47是出现了int类型的越界（Integer.MAX_VALUE is 2147483647）这里需要注意，计算用时达到了恐怖的14秒多。斐波那契数列的值随着增大进行指数级的增长，运行事件也是指数级的增长（n越大越能看出这一点）。

斐波那契数列-递归方法调用过程

动态规划版本

正如鲁迅先生的《狂人日记》中，孔乙己"回"字的四种写法。动态规划算法有两种等价的实现方法。

1. 带备忘的自顶向下法（top-down with memoization），此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或者散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间，否则，按通常的方式计算这个子问题。我们称这个递归过程是带备忘的（memoized）,因为它“记住”了之前计算出的结果。
   以斐波那契数列的解法为例，代码如下：

    long[] memo=new long[memoSize];
    public long topdown(int n) {
        if(n<0) return -1;
        if(n<2) return n;
        if(memo[n]>0) {
            return memo[n];
        }else {
            return memo[n]=topdown(n-1)+topdown(n-2);
        }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0        计算用时        0ms
fibonacci 1 is 1        计算用时        0ms
fibonacci 2 is 1        计算用时        0ms
fibonacci 3 is 2        计算用时        1ms
fibonacci 4 is 3        计算用时        0ms
fibonacci 5 is 5        计算用时        0ms
fibonacci 6 is 8        计算用时        0ms
fibonacci 7 is 13       计算用时        0ms
fibonacci 8 is 21       计算用时        0ms
fibonacci 9 is 34       计算用时        0ms
fibonacci 10 is 55      计算用时        0ms
fibonacci 11 is 89      计算用时        0ms
fibonacci 12 is 144     计算用时        0ms
fibonacci 13 is 233     计算用时        0ms
fibonacci 14 is 377     计算用时        0ms
fibonacci 15 is 610     计算用时        0ms
fibonacci 16 is 987     计算用时        0ms
fibonacci 17 is 1597        计算用时        0ms
fibonacci 18 is 2584        计算用时        0ms
fibonacci 19 is 4181        计算用时        0ms
fibonacci 20 is 6765        计算用时        0ms
fibonacci 21 is 10946       计算用时        0ms
fibonacci 22 is 17711       计算用时        0ms
fibonacci 23 is 28657       计算用时        0ms
fibonacci 24 is 46368       计算用时        0ms
fibonacci 25 is 75025       计算用时        0ms
fibonacci 26 is 121393      计算用时        0ms
fibonacci 27 is 196418      计算用时        0ms
fibonacci 28 is 317811      计算用时        0ms
fibonacci 29 is 514229      计算用时        0ms
fibonacci 30 is 832040      计算用时        0ms
fibonacci 31 is 1346269     计算用时        0ms
fibonacci 32 is 2178309     计算用时        0ms
fibonacci 33 is 3524578     计算用时        0ms
fibonacci 34 is 5702887     计算用时        0ms
fibonacci 35 is 9227465     计算用时        0ms
fibonacci 36 is 14930352        计算用时        0ms
fibonacci 37 is 24157817        计算用时        0ms
fibonacci 38 is 39088169        计算用时        0ms
fibonacci 39 is 63245986        计算用时        0ms
fibonacci 40 is 102334155       计算用时        0ms
fibonacci 41 is 165580141       计算用时        0ms
fibonacci 42 is 267914296       计算用时        0ms
fibonacci 43 is 433494437       计算用时        0ms
fibonacci 44 is 701408733       计算用时        0ms
fibonacci 45 is 1134903170      计算用时        0ms
fibonacci 46 is 1836311903      计算用时        0ms
fibonacci 47 is 2971215073      计算用时        0ms

2. 自底向上法（bottom-up method），这种方法一般需要恰当定义子问题的“规模”的概念，使得任何子问题的求解只依赖“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。每个子问题只需求解依次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。

动态规划的解法-自底向上法

    long[] memo=new long[memoSize];
    public long     bottomup(int n) {
        if(n<0) return -1;
        if(n<=1) return n;
        memo[0]=0;
        memo[1]=1;
        if(n>1) {
            for(int i=2;i<=n;i++) {
                memo[i]=memo[i-1]+memo[i-2];
            }
        }
        return memo[n];
    }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0        计算用时        0ms
fibonacci 1 is 1        计算用时        0ms
fibonacci 2 is 1        计算用时        0ms
fibonacci 3 is 2        计算用时        0ms
fibonacci 4 is 3        计算用时        0ms
fibonacci 5 is 5        计算用时        0ms
fibonacci 6 is 8        计算用时        0ms
fibonacci 7 is 13       计算用时        0ms
fibonacci 8 is 21       计算用时        0ms
fibonacci 9 is 34       计算用时        0ms
fibonacci 10 is 55      计算用时        0ms
fibonacci 11 is 89      计算用时        0ms
fibonacci 12 is 144     计算用时        0ms
fibonacci 13 is 233     计算用时        0ms
fibonacci 14 is 377     计算用时        0ms
fibonacci 15 is 610     计算用时        0ms
fibonacci 16 is 987     计算用时        0ms
fibonacci 17 is 1597        计算用时        0ms
fibonacci 18 is 2584        计算用时        0ms
fibonacci 19 is 4181        计算用时        0ms
fibonacci 20 is 6765        计算用时        0ms
fibonacci 21 is 10946       计算用时        0ms
fibonacci 22 is 17711       计算用时        0ms
fibonacci 23 is 28657       计算用时        0ms
fibonacci 24 is 46368       计算用时        0ms
fibonacci 25 is 75025       计算用时        0ms
fibonacci 26 is 121393      计算用时        0ms
fibonacci 27 is 196418      计算用时        0ms
fibonacci 28 is 317811      计算用时        0ms
fibonacci 29 is 514229      计算用时        0ms
fibonacci 30 is 832040      计算用时        0ms
fibonacci 31 is 1346269     计算用时        0ms
fibonacci 32 is 2178309     计算用时        0ms
fibonacci 33 is 3524578     计算用时        0ms
fibonacci 34 is 5702887     计算用时        0ms
fibonacci 35 is 9227465     计算用时        0ms
fibonacci 36 is 14930352        计算用时        0ms
fibonacci 37 is 24157817        计算用时        0ms
fibonacci 38 is 39088169        计算用时        0ms
fibonacci 39 is 63245986        计算用时        0ms
fibonacci 40 is 102334155       计算用时        0ms
fibonacci 41 is 165580141       计算用时        0ms
fibonacci 42 is 267914296       计算用时        0ms
fibonacci 43 is 433494437       计算用时        0ms
fibonacci 44 is 701408733       计算用时        0ms
fibonacci 45 is 1134903170      计算用时        0ms
fibonacci 46 is 1836311903      计算用时        0ms
fibonacci 47 is 2971215073      计算用时        0ms

总结

同样规模的斐波那契数列的计算问题，动态规划版本的都能在很短的时间内计算完毕，递归的解决方案，在小于50的情况下就出现了十几秒的计算情况，动态规划的运行时间的提升很明显。

动态规划解决走台阶问题

有n级台阶，每次上一级或者两级，问有多少种走完n级台阶的方法。

分析：动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上，我们让f(n)表示走上n级台阶的方法数。
那么当n为1时，f(n) = 1,n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。那么当我们要走上n级台阶，必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步，所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2)，我们用dp[n]来表示动态规划表，dp[i],i>0,i<=n,表示到达i级台阶的方法数。

动态规划的解法-自底向上法

    long[] memo=new long[memoSize];
    public long stepBottomup(int n) {
        if(n<0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;

        memo[0]=1;
        memo[1]=2;
        if(n>1) {
            for(int i=2;i<n;i++) {
                memo[i]=memo[i-1]+memo[i-2];
            }
        }
        return memo[n-1];

    }

通过控制台验证下算法的计算结果和计算用时。

走台阶方案数      楼梯数 1    走法 is 1        计算用时        0ms
走台阶方案数      楼梯数 2    走法 is 2        计算用时        0ms
走台阶方案数      楼梯数 3    走法 is 3        计算用时        0ms
走台阶方案数      楼梯数 4    走法 is 5        计算用时        0ms
走台阶方案数      楼梯数 5    走法 is 8        计算用时        0ms
走台阶方案数      楼梯数 6    走法 is 13       计算用时        0ms
走台阶方案数      楼梯数 7    走法 is 21       计算用时        0ms
走台阶方案数      楼梯数 8    走法 is 34       计算用时        0ms
走台阶方案数      楼梯数 9    走法 is 55       计算用时        0ms
走台阶方案数      楼梯数 10   走法 is 89       计算用时        0ms
走台阶方案数      楼梯数 11   走法 is 144      计算用时        0ms
走台阶方案数      楼梯数 12   走法 is 233      计算用时        0ms
走台阶方案数      楼梯数 13   走法 is 377      计算用时        0ms
走台阶方案数      楼梯数 14   走法 is 610      计算用时        0ms
走台阶方案数      楼梯数 15   走法 is 987      计算用时        0ms
走台阶方案数      楼梯数 16   走法 is 1597     计算用时        0ms
走台阶方案数      楼梯数 17   走法 is 2584     计算用时        0ms
走台阶方案数      楼梯数 18   走法 is 4181     计算用时        0ms
走台阶方案数      楼梯数 19   走法 is 6765     计算用时        0ms
走台阶方案数      楼梯数 20   走法 is 10946        计算用时        0ms
走台阶方案数      楼梯数 21   走法 is 17711        计算用时        0ms
走台阶方案数      楼梯数 22   走法 is 28657        计算用时        0ms
走台阶方案数      楼梯数 23   走法 is 46368        计算用时        0ms
走台阶方案数      楼梯数 24   走法 is 75025        计算用时        1ms
走台阶方案数      楼梯数 25   走法 is 121393       计算用时        0ms
走台阶方案数      楼梯数 26   走法 is 196418       计算用时        0ms
走台阶方案数      楼梯数 27   走法 is 317811       计算用时        0ms
走台阶方案数      楼梯数 28   走法 is 514229       计算用时        0ms
走台阶方案数      楼梯数 29   走法 is 832040       计算用时        0ms
走台阶方案数      楼梯数 30   走法 is 1346269      计算用时        0ms
走台阶方案数      楼梯数 31   走法 is 2178309      计算用时        0ms
走台阶方案数      楼梯数 32   走法 is 3524578      计算用时        0ms
走台阶方案数      楼梯数 33   走法 is 5702887      计算用时        0ms
走台阶方案数      楼梯数 34   走法 is 9227465      计算用时        0ms
走台阶方案数      楼梯数 35   走法 is 14930352     计算用时        0ms
走台阶方案数      楼梯数 36   走法 is 24157817     计算用时        0ms
走台阶方案数      楼梯数 37   走法 is 39088169     计算用时        0ms
走台阶方案数      楼梯数 38   走法 is 63245986     计算用时        0ms
走台阶方案数      楼梯数 39   走法 is 102334155        计算用时        0ms
走台阶方案数      楼梯数 40   走法 is 165580141        计算用时        0ms
走台阶方案数      楼梯数 41   走法 is 267914296        计算用时        0ms
走台阶方案数      楼梯数 42   走法 is 433494437        计算用时        0ms
走台阶方案数      楼梯数 43   走法 is 701408733        计算用时        1ms
走台阶方案数      楼梯数 44   走法 is 1134903170       计算用时        0ms
走台阶方案数      楼梯数 45   走法 is 1836311903       计算用时        0ms
走台阶方案数      楼梯数 46   走法 is 2971215073       计算用时        0ms
走台阶方案数      楼梯数 47   走法 is 4807526976       计算用时        0ms

这里只给出其中的一种解法，至于另一种解法，大家尝试的写下。

以上，谢谢阅读，希望你有所收获！

算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法

参考链接
动态规划算法经典案例