动态规划

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

简而言之，就是将一个大问题拆分成若干的子问题，即分而治之，通过解决逐个逐个小问题进而得到整个问题解的过程。允许这些子问题不独立。此外，也应该需要过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。

因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

斐波拉契数列

Fibonacci数列算是大学算法的通俗例子了。其概念整合成表达式如下：

f(n) = f(n-1)+f(n-2);
其中，f(0)=0,f(1)=1;

递归就是这样一种思路，首先，需要确定递归函数的临界条件是什么，如上n=0或n=1的条件。

通过代码表示如下：（Java，以下皆是）：

    public int fib(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        return simpleFibonacci(n-1)+simpleFibonacci(n-2);
    }

这样就表示出了Fibonacci函数。

但是，有个问题，重复的计算过多。

比如：计算fib(6)的结果，首先需要计算fib(5)和fib(4)的结果，计算fib(5)及又要计算fib(4)和fib(3)的结果，假设之前已经计算出了fib(4)的结果，那么计算fib(5)时又得计算fib(4)一次，以此类推，如下。

可见，重复得计算会很多。一种解决方案是做个备份，也就是说在计算出某个子问题的结果后，需要将其保存，进而避免重复的计算。所以，上面的代码可以优化成这样：

    /**     * 用一个map作为备份来保存每次计算的结果     */
    Map backup = new HashMap<>();
    public int backFibonacci(int n){
        //如果备份有该数据，则直接获取该值，无需计算
        if (backup.containsKey(n)){
            return backup.get(n);
        }
        if (n==0){
            backup.put(0,0);
            return 0;
        }
        if (n==1){
            backup.put(1,1);
            return 1;
        }
        int ret = backFibonacci(n-1)+backFibonacci(n-2);
        //将计算结果保存
        backup.put(n,ret);
        return ret;
    }

求钢条分割的例子

from:https://blog.csdn.net/u013309870/article/details/75193592

同样的，考虑到，一段n的钢条，假设其最优解的为f(n)，那么必定满足：

f(n) = max(Pn,Pi+Pn-i)

这样，我们只需考虑将整个n先分成两段，一段i，一段n-i。（极限值就是i=n）。假设Pi的价格已经是最优解，这样，我们只需要Pn-i的最优解了，最后再通过比较，得出最终的最优解。

所以，代码如下：

/**
     * 钢条切割的map,
     * key : 长度
     * value ：为长度对应的钱
     */
    static Map gtqgMap = new HashMap<>();
    /**
     * 计算出n=i的最优解保存在此处
     */
    static Map gtqgMapBack = new HashMap<>();
    /**
     * 初始临界条件
     */
    static {
        gtqgMap.put(1,2);
        gtqgMap.put(2,5);
        gtqgMap.put(3,8);
        gtqgMap.put(4,9);
        gtqgMap.put(5,10);
        gtqgMap.put(6,17);
        gtqgMap.put(7,17);
        gtqgMap.put(8,20);
        gtqgMap.put(9,24);
        gtqgMap.put(10,30);
    }
       public int gangTiaoQieGeBack(int n){
        if (gtqgMapBack.containsKey(n)){
            return gtqgMapBack.get(n);
        }
        int p = 0;
        if (gtqgMap.containsKey(n)){
            p = gtqgMap.get(n);
        }
        for (int i=1;i

动态规划算法