介绍

动态规划（简称DP）是一种通过存储部分结果从而实现高效递归算法的算法，它本质上来说是一种用空间去换取时间的策略；思想是把一个大问题进行拆分，细分为多个小的子问题，并且能够从这些小的子问题的解中推导出原问题的解，这个大的问题要满足一下两个重要性质才能运用动态规划算法来解决：

• 最优子结构（即大问题拆分后的小问题的解是仍然是最优解）
• 子问题重叠，即拆分后的子问题并不总是新的问题，这些问题会被重复多次计算。
  动态规划正是将每个子问题的解存储在表中，再次遇到相同的问题时只需要查表而不需要重新计算，从而获得高效的算法。

解题步骤

• 分析最优解性质，并刻画其结构特征
• 构造最优值的递归关系表达式
• 自底向上或者自顶向下地计算出最优解
• 根据计算的最优解，构造原问题最优解

示例一

最长递增子序列

题目描述：
在数字序列A中，按下标递增的顺序选出一个子序列B，如果选出的子序列B是严格递增的，则该子序列B称为原数字序列A的递增子序列。最长递增子序列问题就是找到原数字序列A中最长的递增子序列。例如数字序列5,2,8,6,3,6,9,7的一个最长递增子序列为2,3,6,9。

问题分析

设A[i]表示原序列，设DP[i]表示以第i个数结尾的最长上升序列的长度，那么很显然想导出DP[i]的值，需要在DP[k] (1<=k<i)中找出满足a[k]<a[i]最大的那项。假设第k项是我们找到的答案，那么第i个数就可以连接在第k个数之后，成为以第i个数结尾的最长上升序列。如果没有找到答案，换言之第i个数比前面的数都要小，那么DP[i]=1，即生成了从自己开始又以自己结尾的最长升序列。综上，我们很容易得出递推关系表达式：
DP[i]=max(DP[j]+1) 下标为1 <= j < i中，存在A[j] < A[i]
边界条件：DP[i]=1 (i = 1或者不存在A[j] < A[i] 1 <= j < i)
算法复杂度为O(n^2)

具体代码

public class DPTest
{

private int[] A;
DPTest(int[] A){
    this.A = A;
}
public void maxInrenment(){
    int n = A.length;
    int [] lens = new int[n];
    //用于存储递增子序列
    int [][] lenSArr = new int[n][n];
    //初始化
    for(int i = 0;i < n; i++){
        lens[i] = 1;
        //初始化第i个元素的递增序列
        lenSArr[i][0] = A[i];
    }
    for(int i=0;i<n;i++){
      for(int j = i-1;j>=0;j--){
          if(A[i] > A[j] && lens[j]+1>lens[i]){
              lens[i] = lens[j]+1;
              //将第j元素的递增序列拷贝至第i个元素的递增序列
              for(int k = 0;k<=lens[j];k++){
                  lenSArr[i][k] = lenSArr[j][k];
              }
              //在第i个元素递增序列末尾添加第i个元素本身
              lenSArr[i][lens[i]-1]= A[i];
          }
      }
    }
    int index = 0;
    for(int i=0; i<n;i++){
        if(lens[i]>lens[index]){
            index=i;
        }
    }
    System.out.println("最长递增子序列长度："+lens[index]);
    System.out.print("最长递增子序列为：");
    for(int i = 0;i<lens[index];i++){
        System.out.print(lenSArr[index][i]+" ");
    }
    System.out.println();
}

public static void main(String[] args){

    int[] arr = new int[] {2,1,3,4,2,5,7,8,3,6,9};
    DPTest test = new DPTest(arr);
    test.maxInrenment();

}}