动态规划经典案例

​ 动态规划是算法中比较重要的一课，是一种典型的空间换取时间的算法。通常是可以用分治法取考虑一个动态规划问题，用递归实现代码上看起来更加浅显易懂。但是基于递归的实现都是n2的复杂度，这样的复杂度在递归栈到达一定深度的时候会变的非常慢，并且有非常多的重复操作。动态规划致力于将这类递归问题，通过空间换取时间，用容器的方式记录递归结果，减少了重复递归，同时降低了时间复杂度。

最长子数组问题

​ 找出一个数组的连续子数组的最大和。最先想到的solution应该是n2的两次遍历。但是这样的循环是非常耗时的。我们尝试用分治的方式去思考一个复杂的问题，这是算法设计过程中常用的思维。当我们考虑一个任意数组比如{10,-1,2,-4,3,-5,10}，找出最长的子数组。可以先找出{10,-1,2,-4,3,-5}的最长子数组，那么我们可以得到一个数学函数公式（今天想偷个懒，明早去公司画一画）：

​

递归

​ 通常得出递归数学公式之后我们可以直接写出一个直观的递归程序。递归程序如下，这里需要维护一个Sum类，需要记录最长子数组的起始元素位置：

package MaxSubArray;

/**
 * Created by yqz on 8/21/18.
 */
public class Sum {
    private Integer startIndex;
    private Integer sum;
    public Integer getStartIndex() {
        return startIndex;
    }
    public void setStartIndex(Integer startIndex) {
        this.startIndex = startIndex;
    }
    public Integer getSum() {
        return sum;
    }
    public void setSum(Integer sum) {
        this.sum = sum;
    }
}

递归程序：

public class MaxSubArray {
    public static void main(String[] args){
        Integer[] integerArray={10,-1,2,-4,3,-5,10};
        System.out.println(maxSubArray(integerArray,6).getSum());
    }
}
private static Sum maxSubArray(Integer[] integers, Integer index){
        Sum sum=new Sum();
        if(integers==null){
            return null;
        }else if(integers!=null && index==0){
            sum.setStartIndex(0);
            sum.setSum(integers[0]);
            return sum;
        }else{
            Sum tempSum=maxSubArray(integers,index-1);//一个递归嘛,调用栈在上面的地方pop哦，没问题哦（在这里递归到0的时候pop执行下面的方法栈）。这里获取到子集的最长子串
            Integer tempSumValue=0;
            Integer tempIndex=0;//最长子串的起始元素。必须记录这个元素，不然无法计算最长子数组到integer[i]的和
            for(int i=tempSum.getStartIndex();i<=index;i++){
                tempSumValue+=integers[i];
            }//计算最长子数组到integer[i]的和
            if(tempSumValue<integers[index]){
                tempIndex=index;
            }else{
                tempIndex=tempSum.getStartIndex();
            }
            Integer maxSum=max(max(tempSumValue,integers[index]),tempSum.getSum());//取三种情况的最大值
            sum.setStartIndex(tempIndex);//设置当前递归数组的起始元素和最大数组和
            sum.setSum(maxSum);
            return sum;
        }
    }

动态规划（DP）

​ 分析上面的递归程序，n2的效率+递归调用栈，空间和时间利用率都不高。我们通过动态规划进行优化，动态规划的精髓可以用空间去换取空间。

public class MaxSubArray {
    public static void main(String[] args){
        Integer[] integerArray={10,-1,2,-4,3,-5,10};
        int MaxSum = integerArray[0];
        int TempMaxSum = integerArray[0];
        for(int i = 1;i < integerArray.length;i++)//n的复杂度
        {
          TempMaxSum = max(integerArray[i],TempMaxSum + integerArray[i]);//决定当前最大子数组以哪个元素开头
          MaxSum = max(MaxSum,TempMaxSum);
        }
        System.out.println(MaxSum);
    }
}

斐波那契数列问题

​ 斐波那契数列的性质可以得到如下的数学递推公式，同样，我们提供递归和动态规划两种实现方式，这里我们看一下递推的公式：

​

递归+DP

package Fobi;

import java.util.ArrayList;

/**
 * Created by yqz on 8/22/18.
 */
public class FoboNaCiArray {
    public static void main(String[] args) {
        System.out.println(fiboNaciDigui(6));//递归的求斐波那契数列
        //DP求斐波那契数列
        ArrayList<Integer> arrayList=new ArrayList();
        arrayList.add(0);
        arrayList.add(1);
        System.out.println(fiboNaciDP(6,arrayList));
    }
    private static Integer fiboNaciDigui(Integer i){
        if(i==1){
            return 0;
        }else if(i==2){
            return 1;
        }else{
            return fiboNaciDigui(i-1)+fiboNaciDigui(i-2);
        }
    }
    private static Integer fiboNaciDP(Integer index,ArrayList<Integer> arrayList){
        for(int i=2;i<index;i++){
            arrayList.add(arrayList.get(i-1)+arrayList.get(i-2));
        }
        return arrayList.get(index-1);
    }
}