动态规划

之前的文章有提到过动态规划： 动态规划一般用来求最值问题，题型可分为：

1. 子序列
2. 坐标型&双序列
3. 划分型动态规划
4. 状态压缩动态规划

而在其中有一类题型为子序列问题，比如求最长子序列的长度什么的。子序列问题考察动态规划技巧，时间复杂度一般为 O ( n 2 ) O(n^2) O(n2)

两种套路

1. 一维dp数组、两层for循环
2. 二维dp数组、两层for循环

一维数组、两层for循环

int n = array.length;
int[] dp = new int[n];

for (int i = 1; i < n; i++) {
          
   
    for (int j = 0; j < i; j++) {
          
   
        dp[i] = 最值(dp[i], dp[j] + ...)
    }
}

例子：leecode 300： 这里 d p [ i ] dp[i] dp[i] 代表以 n u m s [ i ] nums[i] nums[i] 结尾的递增子序列长度，注意：子序列的元素可以不连续，且 n u m s [ i ] nums[i] nums[i] 不一定属于这个递增子序列。

二维dp数组、两层for循环

这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。

int n = arr.length;
int[][] dp = new dp[n][n];

for (int i = 0; i < n; i++) {
          
   
    for (int j = 1; j < n; j++) {
          
   
        if (arr[i] == arr[j]) 
            dp[i][j] = dp[i][j] + ...
        else
            dp[i][j] = 最值(...)
    }
}

涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：在子数组 a r r 1 [ 0.. i ] arr1[0..i] arr1[0..i] 和子数组 a r r 2 [ 0.. j ] arr2[0..j] arr2[0..j] 中，我们要求的子序列（最长公共子序列）长度为 d p [ i ] [ j ] dp[i][j] dp[i][j] 。 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列）， d p dp dp 数组的含义如下：在子数组 a r r a y [ i . . j ] array[i..j] array[i..j] 中，我们要求的子序列（最长回文子序列）的长度为 d p [ i ] [ j ] dp[i][j] dp[i][j] 。

第一种情况例子：编辑距离 和 最长公共子序列。 第二种情况例子：最长回文子序列