普通子序列

二分优化+子序列 最长上升子序列II

最长公共子序列dp 最长公共子序列

两种子序列转换 最短编辑距离

LC_300. 最长递增子序列

思路

经典的线性DP问题

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int n = nums.length;
  4.         int[] f = new int[n + 1];
  6.         for(int i = 1; i <= n; i ++)f[i] = 1;
  7.         int maxv = 1;
  8.         for (int i = 2; i <= n; i++){
  9.             for (int j = i - 1; j >= 1; j--){
  11.                 if (nums[i - 1] > nums[j - 1]){
  12.                     f[i] = Math.max(f[i], f[j] + 1);
  13.                     maxv = Math.max(maxv, f[i]);
  14.                 }
  15.             }
  16.         }
  17.         return maxv;
  18.     }
  19. }

二分求最长长度o（nlogn）

334. 递增的三元子序列

思路

F1：线性dp

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         //直接线性dp，判断最后结果>=3，就代表存在对应的递增子序列
  4.         int n = nums.length;
  5.         int[] f = new int[n + 1];
  7.         int res = 1;f[1] = 1;
  8.         for (int i = 2; i <= n; i++){
  9.             f[i] = 1;
  10.             for (int j = i - 1; j >= 1; j--){
  11.                 if (nums[i - 1] > nums[j - 1]){
  12.                     f[i] = Math.max(f[i], f[j] + 1);
  13.                     res = Math.max(res, f[i]);
  14.                 }
  15.             }
  16.         }
  17.         return res >= 3;
  18.     }
  19. }

F2：哨兵

设置两个哨兵作为数组的最大和次大值。从后向前扫，如果有一个值比两个哨兵还小，就说明存在对应的子序列

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         //设置两个哨兵作为数组的最大和次大值。从后向前扫，如果有一个值比两个哨兵还小，就说明存在对应的子序列
  4.          int n = nums.length;
  5.         int largest = Integer.MIN_VALUE, larger = Integer.MIN_VALUE;
  6.         for (int i = n - 1; i >= 0; i --){
  7.             if (nums[i] >= largest) largest = nums[i];
  8.             else if (nums[i] >= larger) larger = nums[i];
  9.             else return true;
  10.         }
  11.         return false;
  12.     }
  13. }

354. 俄罗斯套娃信封问题

思路

正常的二维线性dp

  1. class Solution {
  2.     public int maxEnvelopes(int[][] envelopes) {
  3.         //相当于是一个二维的最长上升子序列问题,结合334题优化的思路，从前向后扫描
  4.         //单项扫描不能求最大长度，还是需要dp
  5.         int n = envelopes.length;
  6.         int[] f = new int[n + 1];
  7.         Arrays.sort(envelopes, (int[] a, int[] b)->a[0] - b[0]);
  8.         int count = 1;
  9.         for (int i = 0; i <= n; i ++)f[i] = 1;
  10.         for (int i = 2; i <= n; i ++){
  11.             for (int j = i - 1; j >= 1; j--){
  12.                 if (envelopes[j - 1][0] < envelopes[i - 1][0] && 
  13.                     envelopes[j - 1][1] < envelopes[i - 1][1]
  14.                 )
  15.                     f[i] = Math.max(f[i], f[j] + 1);
  16.                     count = Math.max(f[i], count);
  17.             }
  18.         }
  19.         return count;
  20.     }
  21. }

376. 摆动序列

思路

局部极值个数

线性DP - 图1

我们能看到，摆动序列除了两端点，每个值都是局部极值。推想：原序列去除连续相同的数，取两端点和极值部分，就是最长的摆动序列。

如果这样的不是最长的摆动序列，就意味着从原序列能找出来更多的极值。这是不可能的。

如果点不是在极值点上取得，只能在极值两边线段上取得，而取得的点不可能比极值点还多。

那么我们找一个数a[i] 有a[i] >= a[i - 1] && a[i] > a[i + 1]，a[i]就是极大值

同样也能找到极小值，遍历一遍

有一个样例过不了
class Solution {
    public int wiggleMaxLength(int[] nums) {
        //摆动序列
        int n = nums.length, count = 0;
        if (n < 2) return n;
        count = (nums[1] - nums[0] == 0) ? 1 : 2;
        for (int i = 1; i < n - 1; i ++){
            if (nums[i] <= nums[i - 1] && nums[i] < nums[i + 1])count ++;
            if (nums[i] >= nums[i - 1] && nums[i] > nums[i + 1]) count ++;
        }
        return count;
    }
}

动态规划：

线性DP - 图2

线性DP - 图3

简化代码，因为每一次只用到了前一次的状态。


class Solution {
    public int wiggleMaxLength(int[] nums) {
        //摆动序列
        int n = nums.length, count = 0;
        //去除重复数
        int up = 1, down = 1;
        for (int i = 1; i < n; i ++){
            if (nums[i] > nums[i - 1]) up = down + 1;
            if (nums[i] < nums[i - 1]) down = up + 1;
        }
        return Math.max(up, down);
    }
}

673. 最长递增子序列的个数

有些混乱的思路

当时想的是先求出最大值，开一个g[i]存放 以nums[i]解为的最长子序列的个数。

结果用了一次二分 又用了一次dp

由于求g[]的时候需要使用 以nums[i]结尾的最长子序列的长度，因此需要使用f[]数组

那么第一次二分求最长子序列是冗余的。

并且需要考虑

线性DP - 图4%20%20%5C%5C%0Ag%5Bi%5D%20%2B%3D%20g%5Bj%5D%20%26%20(f%5Bi%5D%20%3D%3D%20f%5Bj%5D%20%2B%201%20)%0A%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%0A%20g%5Bi%5D%20%3D%20g%5Bj%5D%20%26%20%28f%5Bi%5D%20%3C%20f%5Bj%5D%20%2B%201%29%20%20%5C%5C%0Ag%5Bi%5D%20%2B%3D%20g%5Bj%5D%20%26%20%28f%5Bi%5D%20%3D%3D%20f%5Bj%5D%20%2B%201%20%29%0A%5Cend%7Bcases%7D%0A)

两种情况.

第一种表示第i个元素作为 最长子序列的结尾的个数是和 子序列中上一个元素

是一样的。

第二种表示第i个元素作为 最长子序列的结尾 能找到 不同的序列,那么需要加上对应的个数。

class Solution {
    public int findNumberOfLIS(int[] nums) {
        //二分 
        int n = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        list.add(Integer.MIN_VALUE);
        for (int i = 0; i < n; i ++){
            int l = 0, r = list.size() - 1;
            while (l < r){
                int mid = mid =(l + r + 1) / 2;
                if (list.get(mid) < nums[i]) l = mid;
                else r = mid - 1;
            }
            if (r + 1 > list.size() - 1) list.add(nums[i]);
            else list.set(r + 1, nums[i]);
        }
        int maxv = list.size();
        System.out.println(maxv);
        if (maxv == 1)return n;


        int[] nums2 = new int[n + 1];nums2[0] = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i ++)
            nums2[i + 1] = nums[i];
        int[] f = new int[n + 2]; int res = 0;
        int[] g = new int[n + 2];
        f[1] = 1;g[1] = 1;
        for (int i = 2; i <= n + 1; i ++){
            f[i] = 1;
            for (int j = i - 1; j >= 1; j--){
                if (nums2[i - 1] > nums2[j - 1]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                    if (f[i] == f[j] + 1) g[i] += g[j];
                }
            }
        }
        for (int i = 1; i <= n + 1; i++)
            if (f[i] == maxv) res += g[i];
    return res;
    }
}

正确的代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1]; int res = 0;
        int[] g = new int[n + 1];
        f[1] = 1;g[1] = 1;
        int maxv = 1;
        for (int i = 2; i <= n; i ++){
            f[i] = 1;g[i] = 1;
            for (int j = i - 1; j >= 1; j--){
                if (nums[i - 1] > nums[j - 1]) {
                    if(f[i] < f[j] + 1){
                        g[i] = g[j];
                        f[i] = f[j] + 1;
                    }
                    else if (f[i] == f[j] + 1) g[i] += g[j];
                    maxv = Math.max(maxv, f[i]);
                }
            }
        }
        System.out.println(maxv);
        for (int i = 1; i <= n; i++)
            if (f[i] == maxv) res += g[i];
    return res;
    }
}

以j结尾的最大子序和 53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        //f[j] 表示以j结尾的最大子序和
        // f[j] = max(f[j-1]+nums[j-1],nums[j-1])
        //起始条件 f[1]=nums[0]
        //最终答案是 max(f[1],f[2]....f[n])
        int n = nums.length;
        int[] f = new int[n + 1];
        f[1]=nums[0];
        //状态转移
        for (int j = 2; j <= n; j++)
            f[j]=Math.max(f[j-1]+nums[j-1], nums[j-1]);
        int maxv = Integer.MIN_VALUE;
        //计算结果
        for (int j = 1; j <= n; j++)
            maxv = Math.max(maxv,f[j]);
        return maxv;
    }
}

统计个数 = 线性dp59. 把数字翻译成字符串

class Solution {
    public int getTranslationCount(String s) {
        //动态规划：
        /*
            f[i]:以i结尾的字符串中翻译方法总数
            f[i] = f[i - 1] + f[i - 2](如果s[i-1]s[i]能翻译成字符)
            f[0] = 1, f[1] = 1;
            res : f[n];
            特殊情况：去除0开头的情况
        */
        int n = s.length();
        if (n ==0) return 1;
        int[] f= new int[n + 1]; 
        f[0] = 1;f[1] = 1;
        for (int i = 2; i <= n; i ++){
            f[i] += f[i - 1];
            int weight = s.charAt(i - 2) - '0';
            weight = weight * 10 + s.charAt(i - 1) - '0';
            if (s.charAt(i - 2) != '0' && weight >= 0 && weight <= 25)
                f[i] += f[i - 2];
        }
        return f[n];
    }
}

线性dp求方案数 80. 骰子的点数

定义状态数组f[i][j] 表示投掷i次，掷出j点d的掷法

状态转移：f[i][j] += f[i - 1][j - k](k ->[1,6]) 点数跟随最后一次的投掷而变动，
因此f[i][j]应该是最后一次投掷到j点的方案数的总和
边界：初始的时候代表一种方案

class Solution {
    public int[] numberOfDice(int n) {
        //定义状态数组f[i][j] 表示投掷i次，掷出j点d的掷法
        /* 
            状态转移：f[i][j] += f[i - 1][j - k](k ->[1,6]) 点数跟随最后一次的投掷而变动，
            因此f[i][j]应该是最后一次投掷到j点的方案数的总和
            边界：初始的时候代表一种方案
        */
        int[][] f = new int[n + 1][6 *n + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++){
            for (int j = i; j <= 6 * n; j ++)
                for (int k = 1; k <= Math.min(6, j); k ++)
                    f[i][j] += f[i - 1][j - k];
        }
        int[] res = new int[6*n-n+1];
        for (int i = n; i <= 6*n; i ++)
            res[i - n] = f[n][i];
        return res;
    }
}