面试算法大全-动态规划总结

亦凉 2022-10-17 13:51 217阅读 0赞

动态规划三要素：（1）重叠子问题，（2）最优子结构，（3）状态转移方程。

思考状态转移方程：明确\[状态\]—>定义dp数组/函数的含义—>明确选择—>明确base case

动态规划解题范例：  
斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1)，生成第 n 项的做法有以下几种：

**递归法：**  
原理： 把 f(n)问题的计算拆分成 f(n-1和 f(n-2)两个子问题的计算，并递归，以 f(0)和 f(1)为终止条件。  
缺点： 大量重复的递归计算，例如 f(n)和 f(n - 1)两者向下递归需要 各自计算 f(n−2) 的值。

public int fib(int N){
        
            if (N==1||N==2){
        
                return 1;
            }
            return fib(N-1)+fib2(N-2);
        }

**记忆化递归法：**  
原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n)的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。  
缺点： 记忆化存储需要使用 O(N) 的额外空间。

/**
         * 带备忘录的剪枝操作
         * @param n
         * @return
         */
        public int fib2(int n){
        
            HashMap<Integer, Integer> hashmap = new HashMap<>();
            if (n==1||n==2){
        
                return 1;
            }
            if (hashmap.get(n)!=null){
        
                return hashmap.get(n);
            }
            int res=fib(n-1)+fib(n-2);
            hashmap.put(n,res);
            return res;
        }

**动态规划：**  
原理： 以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。

/**
         * 动态规划的递推形式
         * @param N
         */
        public int fib3(int N){
        
            //dp table
            int[] dp=new int[N+1];
            dp[1]=dp[2]=1;
            for (int i=3;i<=N;i++) {
        
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[N];
        }

降低空间复杂度

/**
         * 只需要记住两个值
         * @param N
         */
        public int fib4(int N){
        
            if (N==1||N==2){
        
                return 1;
            }
            int pre=1,curr=1;
            for (int i=3;i<=N;i++){
        
                int sum=pre+curr;
                pre=curr;
                curr=sum;
            }
            return curr;
        }

### 10.2 经典题目源码总结 ###

#### [零钱兑换][Link 1] ####

解题四步曲

第一种：递归形式

/**
         * 递归形式
         * @param coins  硬币面值
         * @param amount 目标金额
         * @return
         */
        public int coinChangeRecursive1(int[] coins, int amount) {
        
            if (amount == 0) {
        
                return 0;
            }
            if (amount < 0) {
        
                return -1;
            }
    
            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
        
                int subMin = coinChangeRecursive1(coins, amount - coin);
                if (subMin == -1) {
        
                    continue;
                }
                res = Math.min(res, 1 + subMin);
            }
            if (res == Integer.MAX_VALUE) {
        
                return -1;
            }
            return res;
        }

第二种：带备忘录的形式

/**
         * 带备忘录的形式
         */
        private static HashMap<Integer, Integer> map=new HashMap<>();
        public int coinChangeRecursive2(int[] coins, int amount) {
        
            if (map.get(amount)!=null){
        
                return map.get(amount);
            }
    
            if (amount == 0) {
        
                return 0;
            }
            if (amount < 0) {
        
                return -1;
            }
    
            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
        
                int subMin = coinChangeRecursive2(coins, amount - coin);
                if (subMin == -1) {
        
                    continue;
                }
                res = Math.min(res, 1 + subMin);
            }
            if (res == Integer.MAX_VALUE) {
        
                return -1;
            }
            map.put(amount,res);
            return res;
        }

第三种：自底向上的递推（动态规划）

/**
         * 动态规划形式
         * @param coins
         * @param amount
         * @return
         */
        public int coinChangedp(int[] coins,int amount){
        
            int[] dp=new int[amount+1];
            //初始化数组
            for (int i=0;i<amount+1;i++){
        
                dp[i]=amount+1;
            }
    
            dp[0]=0;
            for (int i=0;i<amount+1;i++){
        
                for (int j=0;j<coins.length;j++){
        
                    if (i>=coins[j]){
        
                        dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
                    }
                }
            }
            if (dp[amount]==amount+1){
        
                return -1;
            }
            return dp[amount];
        }

#### [三角形最小路径和][Link 2] ####

方法一：递归

/**
         * 普通递归
         * @param i
         * @param j
         * @return
         */
        public static int traverse1(int i, int j) {
        
            int totalRow = 4; // 总行数
            if (i >=  totalRow - 1) {
        
                return 0;
            }
            // 往左下节点走时
            int leftSum = traverse1(i+1, j) + triangle[i+1][j];
            // 往右下节点走时
            int rightSum = traverse1(i+1, j+1) + triangle[i+1][j+1];
            // 记录每个节点往左和往右遍历的路径和的最小值
            return Math.min(leftSum, rightSum);
        }

方法二：带备忘录的递归

/**
         * 带备忘录的递归
         * @param i
         * @param j
         */
        private static HashMap<String, Integer> map=new HashMap<>();
        public static int traverse2(int i, int j) {
        
            String key=i+""+j;
            if (map.get(key)!=null){
        
                return map.get(key);
            }
            int totalRow = 4; // 总行数
            if (i >=  totalRow - 1) {
        
                return 0;
            }
            // 往左下节点走时
            int leftSum = traverse2(i+1, j) + triangle[i+1][j];
            // 往右下节点走时
            int rightSum = traverse2(i+1, j+1) + triangle[i+1][j+1];
            // 记录每个节点往左和往右遍历的路径和的最小值
            int result= Math.min(leftSum, rightSum);
            map.put(key,result);
            return result;
        }

方法三：自底向上的递推（动态规划）

public static int traverse3(){
        
        int row=4;
        int[] mini=triangle[row-1];
        for (int i=row-2;i>=0;i--){
        
            for (int j=0;j<triangle[i].length;j++){
        
                mini[j]=triangle[i][j]+Math.min(mini[j],mini[j+1]);
            }
        }
        return mini[0];
    }

#### 0-1背包问题 ####

方法一：递归方法

public class KnapSack01 {
        
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
        
            //基准条件：如果索引无效或者容量不足，直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值（前提是：第index个物品可以放得下）
            if (w[index] <= capacity) {
        
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            return res;
        }
        public static int knapSack(int[] w, int[] v, int C) {
        
            int size = w.length;
            return solveKS(w, v, size - 1, C);
        }
        public static void main(String[] args){
        
            int[] w = {
        2,1,3,2};
            int[] v = {
        12,10,20,15};
            System.out.println(knapSack(w,v,5));
        }
    }

方法二：带备忘录的记忆化搜索

public class KnapSack01 {
        
        private static int[][] memo;
        /**
         * 解决背包问题的递归函数
         *
         * @param w        物品的重量数组
         * @param v        物品的价值数组
         * @param index    当前待选择的物品索引
         * @param capacity 当前背包有效容量
         * @return 最大价值
         */
        private static int solveKS(int[] w, int[] v, int index, int capacity) {
        
            //基准条件：如果索引无效或者容量不足，直接返回当前价值0
            if (index < 0 || capacity <= 0)
                return 0;
            //如果此子问题已经求解过，则直接返回上次求解的结果
            if (memo[index][capacity] != 0) {
        
                return memo[index][capacity];
            }
            //不放第index个物品所得价值
            int res = solveKS(w, v, index - 1, capacity);
            //放第index个物品所得价值（前提是：第index个物品可以放得下）
            if (w[index] <= capacity) {
        
                res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
            }
            //添加子问题的解，便于下次直接使用
            memo[index][capacity] = res;
            return res;
        }
        public static int knapSack(int[] w, int[] v, int C) {
        
            int size = w.length;
            memo = new int[size][C + 1];
            return solveKS(w, v, size - 1, C);
        }
        public static void main(String[] args) {
        
            int[] w = {
        2, 1, 3, 2};
            int[] v = {
        12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }

方法三：动态规划算法

public class KnapSack01 {
        
        public static int knapSack(int[] w, int[] v, int C) {
        
            int size = w.length;
            if (size == 0) {
        
                return 0;
            }
    
            int[][] dp = new int[size][C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
        
                dp[0][i] = w[0] <= i ? v[0] : 0;
            }
    		//填充其他行和列
            for (int i = 1; i < size; i++) {
        
                for (int j = 0; j <= C; j++) {
        
                    dp[i][j] = dp[i - 1][j];
                    if (w[i] <= j) {
        
                        dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
                    }
                }
            }
            return dp[size - 1][C];
        }
    
        public static void main(String[] args) {
        
            int[] w = {
        2, 1, 3, 2};
            int[] v = {
        12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }

方法四：优化空间复杂度

public class KnapSack01 {
        
        public static int knapSack(int[] w, int[] v, int C) {
        
            int size = w.length;
            if (size == 0) {
        
                return 0;
            }
    
            int[] dp = new int[C + 1];
            //初始化第一行
            //仅考虑容量为C的背包放第0个物品的情况
            for (int i = 0; i <= C; i++) {
        
                dp[i] = w[0] <= i ? v[0] : 0;
            }
    
            for (int i = 1; i < size; i++) {
        
                for (int j = C; j >= w[i]; j--) {
        
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
            }
            return dp[C];
        }
    
        public static void main(String[] args) {
        
            int[] w = {
        2, 1, 3, 2};
            int[] v = {
        12, 10, 20, 15};
            System.out.println(knapSack(w, v, 5));
        }
    }

#### [分割等和子集][Link 3](0-1背包变体) ####

方法一：采用动态规划

public boolean canPartition(int[] nums) {
        
        int sum=0;
        for (int i=0;i<nums.length;i++) {
        
            sum+=nums[i];
        }
        if (sum%2!=0){
        
            return false;
        }
        int n=nums.length;
        sum=sum/2;
        boolean[][] dp=new boolean[n+1][sum+1];
        for (int i=0;i<=n;i++){
        
            dp[i][0]=true;
        }
        for (int i = 1; i <= n; i++) {
        
            for (int j = 1; j <= sum; j++) {
        
                if (j - nums[i - 1] < 0) {
        
                    // 背包容量不足，不能装入第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                } else {
        
                    // 装入或不装入背包
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }

方法二：状态压缩（二维数组压缩为一维）

public boolean canPartition2(int[] nums){
        
        int sum=0;
        for (int i=0;i<nums.length;i++) {
        
            sum+=nums[i];
        }
    
        if (sum%2!=0){
        
            return false;
        }
    
        int n=nums.length;
        sum=sum/2;
    
        boolean[] dp=new boolean[sum+1];
        dp[0]=true;
        for (int i = 0; i < n; i++) {
        
            for (int j = sum; j >=0 ; j--) {
        
                if (j-nums[i]>=0){
        
                    dp[j]=dp[j]||dp[j-nums[i]];
                }
            }
        }
        return dp[sum];
    }

#### [零钱兑换 II][II]（完全背包问题） ####

方法一：采用动态规划

int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount];
    }

方法二：空间压缩

int change2(int amount,int[] coins){
        
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1; // base case
        for (int i = 0; i < n; i++) {
        
            for (int j = 1; j <= amount; j++) {
        
                if (j - coins[i] >= 0) {
        
                    dp[j] = dp[j] + dp[j-coins[i]];
                }
            }
        }
        return dp[amount];
    }

#### [完全平方数][Link 4](完全背包问题变体) ####

class Solution {
        
        public int numSquares(int n) {
        
            int[] dp = new int[n + 1]; // 默认初始化值都为0
            for (int i = 1; i <= n; i++) {
        
                dp[i] = i; // 最坏的情况就是每次+1
                for (int j = 1; i - j * j >= 0; j++) {
         
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
                }
            }
            return dp[n];
        }
    }

#### [最长上升子序列][Link 5] ####

方法一：动态规划

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            if (nums.length == 0) {
        
                return 0;
            }
            int[] dp = new int[nums.length];
            dp[0] = 1;
            int maxans = 1;
            for (int i = 1; i < nums.length; i++) {
        
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                maxans = Math.max(maxans, dp[i]);
            }
            return maxans;
        }
    }

方法二：贪心 + 二分查找

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int len = 1, n = nums.length;
            if (n == 0) {
        
                return 0;
            }
            int[] d = new int[n + 1];
            d[len] = nums[0];
            for (int i = 1; i < n; ++i) {
        
                if (nums[i] > d[len]) {
        
                    d[++len] = nums[i];
                } else {
        
                    int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                    while (l <= r) {
        
                        int mid = (l + r) >> 1;
                        if (d[mid] < nums[i]) {
        
                            pos = mid;
                            l = mid + 1;
                        } else {
        
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return len;
        }
    }

#### [最长回文子串][Link 6] ####

class Solution {
        
        public String longestPalindrome(String s) {
        
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            String ans = "";
            for (int l = 0; l < n; ++l) {
        
                for (int i = 0; i + l < n; ++i) {
        
                    int j = i + l;
                    if (l == 0) {
        
                        dp[i][j] = true;
                    } else if (l == 1) {
        
                        dp[i][j] = (s.charAt(i) == s.charAt(j));
                    } else {
        
                        dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                    }
                    if (dp[i][j] && l + 1 > ans.length()) {
        
                        ans = s.substring(i, i + l + 1);
                    }
                }
            }
            return ans;
        }
    }

#### [最长回文子序列][Link 7] ####

class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int n = s.length();
            int[][] f = new int[n][n];
            for (int i = n - 1; i >= 0; i--) {
        
                f[i][i] = 1;
                for (int j = i + 1; j < n; j++) {
        
                    if (s.charAt(i) == s.charAt(j)) {
        
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
        
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
            return f[0][n - 1];
        }
    }

#### [最长公共子序列][Link 8] ####

// java
    class Solution {
        
        public int longestCommonSubsequence(String text1, String text2) {
        
            int m = text1.length(), n = text2.length();
            int[][] dp = new int[m + 1][n + 1];
    
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    // 获取两个串字符
                    char c1 = text1.charAt(i), c2 = text2.charAt(j);
                    if (c1 == c2) {
        
                        // 去找它们前面各退一格的值加1即可
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                    } else {
        
                        //要么是text1往前退一格，要么是text2往前退一格，两个的最大值
                        dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                    }
                }
            }
            return dp[m][n];
        }
    }

#### [统计不同回文子序列][Link 9] ####

class Solution {
        
      public int countPalindromicSubsequences(String S) {
        
        int n = S.length();
        int mod = 1000000007;
        int[][][] dp = new int[4][n][n];
    
        for (int i = n-1; i >= 0; --i) {
        
          for (int j = i; j < n; ++j) {
        
            for (int k = 0; k < 4; ++k) {
        
              char c = (char) ('a' + k);
              if (j == i) {
        
                if (S.charAt(i) == c) dp[k][i][j] = 1;
                else dp[k][i][j] = 0;
              } else {
         // j > i
                if (S.charAt(i) != c) dp[k][i][j] = dp[k][i+1][j];
                else if (S.charAt(j) != c) dp[k][i][j] = dp[k][i][j-1];
                else {
         // S[i] == S[j] == c
                  if (j == i+1) dp[k][i][j] = 2; // "aa" : {"a", "aa"}
                  else {
         // length is > 2
                    dp[k][i][j] = 2;
                    for (int m = 0; m < 4; ++m) {
         // count each one within subwindows [i+1][j-1]
                      dp[k][i][j] += dp[m][i+1][j-1];
                      dp[k][i][j] %= mod;
                    }
                  }
                }
              }
            }
          }
        }
        int ans = 0;
        for (int k = 0; k < 4; ++k) {
        
          ans += dp[k][0][n-1];
          ans %= mod;
        }
        return ans;
      }
    }

#### [不同的子序列][Link 10] ####

class Solution {
        
        public int numDistinct(String s, String t) {
        
            int[][] dp = new int[t.length() + 1][s.length() + 1];
            for (int j = 0; j < s.length() + 1; j++) dp[0][j] = 1;
            for (int i = 1; i < t.length() + 1; i++) {
        
                for (int j = 1; j < s.length() + 1; j++) {
        
                    if (t.charAt(i - 1) == s.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                    else dp[i][j] = dp[i][j - 1];
                }
            }
            return dp[t.length()][s.length()];
        }
    }

#### [不同的子序列 II][II 1] ####

class Solution {
        
        public int distinctSubseqII(String S) {
        
            int MOD = 1_000_000_007;
            int N = S.length();
            int[] dp = new int[N+1];
            dp[0] = 1;
    
            int[] last = new int[26];
            Arrays.fill(last, -1);
    
            for (int i = 0; i < N; ++i) {
        
                int x = S.charAt(i) - 'a';
                dp[i+1] = dp[i] * 2 % MOD;
                if (last[x] >= 0)
                    dp[i+1] -= dp[last[x]];
                dp[i+1] %= MOD;
                last[x] = i;
            }
    
            dp[N]--;
            if (dp[N] < 0) dp[N] += MOD;
            return dp[N];
        }
    }

#### [判断子序列][Link 11] ####

class Solution {
        
        public boolean isSubsequence(String s, String t) {
        
            int n = s.length(), m = t.length();
    
            int[][] f = new int[m + 1][26];
            for (int i = 0; i < 26; i++) {
        
                f[m][i] = m;
            }
    
            for (int i = m - 1; i >= 0; i--) {
        
                for (int j = 0; j < 26; j++) {
        
                    if (t.charAt(i) == j + 'a')
                        f[i][j] = i;
                    else
                        f[i][j] = f[i + 1][j];
                }
            }
            int add = 0;
            for (int i = 0; i < n; i++) {
        
                if (f[add][s.charAt(i) - 'a'] == m) {
        
                    return false;
                }
                add = f[add][s.charAt(i) - 'a'] + 1;
            }
            return true;
        }
    }

#### [最大子序和][Link 12] ####

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
        
                pre = Math.max(pre + x, x);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
    }

#### [连续子数组的最大和][Link 13] ####

方法一：计算

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int res = nums[0];
            for(int i = 1; i < nums.length; i++) {
        
                nums[i] += Math.max(nums[i - 1], 0);
                res = Math.max(res, nums[i]);
            }
            return res;
        }
    }

方法二：动态规划

public int maxSubArray2(int[] nums) {
        
        int n = nums.length;
        if (n == 0) {
        
            return 0;
        }
        int[] dp = new int[n];
        // base case
        // 第一个元素前面没有子数组
        dp[0] = nums[0];
        // 状态转移方程
        for (int i = 1; i < n; i++) {
        
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        // 得到 nums 的最大子数组
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
        
            res = Math.max(res, dp[i]);
        }
        return res;
    }

方法三：空间压缩

public int maxSubArray3(int[] nums){
        
        int n = nums.length;
        if (n == 0) {
        
            return 0;
        }
        // base case
        int dp_0 = nums[0];
        int dp_1 = 0, res = dp_0;
        for (int i = 1; i < n; i++) {
        
            // dp[i] = max(nums[i], nums[i] + dp[i-1])
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;
            // 顺便计算最大的结果
            res = Math.max(res, dp_1);
        }
        return res;
    }

#### [最长重复子数组][Link 14] ####

方法一：动态规划

class Solution {
        
        public int findLength(int[] A, int[] B) {
        
            int n = A.length, m = B.length;
            int[][] dp = new int[n + 1][m + 1];
            int ans = 0;
            for (int i = n - 1; i >= 0; i--) {
        
                for (int j = m - 1; j >= 0; j--) {
        
                    dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            return ans;
        }
    }

方法二：滑动窗口

class Solution {
        
        public int findLength(int[] A, int[] B) {
        
            int n = A.length, m = B.length;
            int ret = 0;
            for (int i = 0; i < n; i++) {
        
                int len = Math.min(m, n - i);
                int maxlen = maxLength(A, B, i, 0, len);
                ret = Math.max(ret, maxlen);
            }
            for (int i = 0; i < m; i++) {
        
                int len = Math.min(n, m - i);
                int maxlen = maxLength(A, B, 0, i, len);
                ret = Math.max(ret, maxlen);
            }
            return ret;
        }
    
        public int maxLength(int[] A, int[] B, int addA, int addB, int len) {
        
            int ret = 0, k = 0;
            for (int i = 0; i < len; i++) {
        
                if (A[addA + i] == B[addB + i]) {
        
                    k++;
                } else {
        
                    k = 0;
                }
                ret = Math.max(ret, k);
            }
            return ret;
        }
    }

#### [戳气球][Link 15] ####

class Solution {
        
        public int maxCoins(int[] nums) {
        
            int n = nums.length;
            int[][] rec = new int[n + 2][n + 2];
            int[] val = new int[n + 2];
            val[0] = val[n + 1] = 1;
            for (int i = 1; i <= n; i++) {
        
                val[i] = nums[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
        
                for (int j = i + 2; j <= n + 1; j++) {
        
                    for (int k = i + 1; k < j; k++) {
        
                        int sum = val[i] * val[k] * val[j];
                        sum += rec[i][k] + rec[k][j];
                        rec[i][j] = Math.max(rec[i][j], sum);
                    }
                }
            }
            return rec[0][n + 1];
        }
    }

#### [一和零][Link 16] ####

public class Solution {
        
        public int findMaxForm(String[] strs, int m, int n) {
        
            int[][] dp = new int[m + 1][n + 1];
            for (String s: strs) {
        
                int[] count = countzeroesones(s);
                for (int zeroes = m; zeroes >= count[0]; zeroes--)
                    for (int ones = n; ones >= count[1]; ones--)
                        dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);
            }
            return dp[m][n];
        }
        public int[] countzeroesones(String s) {
        
            int[] c = new int[2];
            for (int i = 0; i < s.length(); i++) {
        
                c[s.charAt(i)-'0']++;
            }
            return c;
        }
    }

#### [爬楼梯][Link 17] ####

class Solution {
        
        public int climbStairs(int n) {
        
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; i++) {
        
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

空间压缩

class Solution {
        
        public int climbStairs(int n) {
        
            int p = 0, q = 0, r = 1;
            for (int i = 1; i <= n; ++i) {
        
                p = q; 
                q = r; 
                r = p + q;
            }
            return r;
        }
    }

#### [使用最小花费爬楼梯][Link 18] ####

public int minCostClimbingStairs(int[] cost) {
        
        if (cost.length == 0)
            return 0;
        if (cost.length == 1)
            return cost[0];
    
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
    
        for (int i=2; i<cost.length; i++){
        
            dp[i] = Math.min(dp[i-1] + cost[i], dp[i-2] + cost[i]);
        }
        return Math.min(dp[cost.length-1], dp[cost.length-2]);
    }

class Solution {
        
        public int minCostClimbingStairs(int[] cost) {
        
            int f1 = 0, f2 = 0;
            for (int i = cost.length - 1; i >= 0; --i) {
        
                int f0 = cost[i] + Math.min(f1, f2);
                f2 = f1;
                f1 = f0;
            }
            return Math.min(f1, f2);
        }
    }

#### [编辑距离][Link 19] ####

public class Problem_72 {
        
        public int minDistance(String word1, String word2) {
        
            int n=word1.length();
            int m=word2.length();
    
            if (m*n==0){
        
                return n+m;
            }
    
            int[][] dp=new int[n+1][m+1];
    
            for (int i=0;i<n+1;i++){
        
               dp[i][0]=i;
            }
            for (int j=0;j<m+1;j++){
        
                dp[0][j]=j;
            }
    
            for (int i=1;i<n+1;i++){
        
                for (int j=1;j<m+1;j++){
        
                    if (word1.charAt(i-1)==word2.charAt(j-1)){
        
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else {
        
                        dp[i][j]=Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                    }
                }
            }
            return dp[n][m];
        }
    
        public static void main(String[] args) {
        
            String word1 = "horse";
            String word2 = "ros";
    
            Problem_72 problem_72=new Problem_72();
            int minDistance = problem_72.minDistance(word1, word2);
            System.out.println(minDistance);
        }
    }

#### [青蛙过河][Link 20] ####

public class Solution {
        
        public boolean canCross(int[] stones) {
        
            HashMap<Integer, Set<Integer>> map = new HashMap<>();
            for (int i = 0; i < stones.length; i++) {
        
                map.put(stones[i], new HashSet<Integer>());
            }
            map.get(0).add(0);
            for (int i = 0; i < stones.length; i++) {
        
                for (int k : map.get(stones[i])) {
        
                    for (int step = k - 1; step <= k + 1; step++) {
        
                        if (step > 0 && map.containsKey(stones[i] + step)) {
        
                            map.get(stones[i] + step).add(step);
                        }
                    }
                }
            }
            return map.get(stones[stones.length - 1]).size() > 0;
        }
    }

#### [鸡蛋掉落][Link 21] ####

方法一：动态规划

class Solution {
        
        public int superEggDrop(int K, int N) {
        
            if (N == 1) {
        
                return 1;
            }
            int[][] f = new int[N + 1][K + 1];
            for (int i = 1; i <= K; ++i) {
        
                f[1][i] = 1;
            }
            int ans = -1;
            for (int i = 2; i <= N; ++i) {
        
                for (int j = 1; j <= K; ++j) {
        
                    f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
                }
                if (f[i][K] >= N) {
        
                    ans = i;
                    break;
                }
            }
            return ans;
        }
    }

方法二：动态规划+二分搜索

class Solution {
        
        public int superEggDrop(int K, int N) {
        
            return dp(K, N);
        }
        Map<Integer, Integer> memo = new HashMap();
        public int dp(int K, int N) {
        
            if (!memo.containsKey(N * 100 + K)) {
        
                int ans;
                if (N == 0) {
        
                    ans = 0;
                } else if (K == 1) {
        
                    ans = N;
                } else {
        
                    int lo = 1, hi = N;
                    while (lo + 1 < hi) {
        
                        int x = (lo + hi) / 2;
                        int t1 = dp(K-1, x-1);
                        int t2 = dp(K, N-x);
    
                        if (t1 < t2) {
        
                            lo = x;
                        } else if (t1 > t2) {
        
                            hi = x;
                        } else {
        
                            lo = hi = x;
                        }
                    }
                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)), Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));
                }
    
                memo.put(N * 100 + K, ans);
            }
    
            return memo.get(N * 100 + K);
        }
    }

#### [不同路径][Link 22] ####

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            int[][] dp = new int[m][n];
            for (int i = 0; i < n; i++) dp[0][i] = 1;
            for (int i = 0; i < m; i++) dp[i][0] = 1;
            for (int i = 1; i < m; i++) {
        
                for (int j = 1; j < n; j++) {
        
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];  
        }
    }

#### [不同路径 II][II 2] ####

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int n = obstacleGrid.length, m = obstacleGrid[0].length;
            int[] f = new int[m];
    
            f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
            for (int i = 0; i < n; ++i) {
        
                for (int j = 0; j < m; ++j) {
        
                    if (obstacleGrid[i][j] == 1) {
        
                        f[j] = 0;
                        continue;
                    }
                    if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
        
                        f[j] += f[j - 1];
                    }
                }
            }
            
            return f[m - 1];
        }
    }

#### [最小路径和][Link 23] ####

class Solution {
        
        public int minFallingPathSum(int[][] A) {
        
            int N = A.length;
            for (int r = N-2; r >= 0; --r) {
        
                for (int c = 0; c < N; ++c) {
        
                    // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                    int best = A[r+1][c];
                    if (c > 0)
                        best = Math.min(best, A[r+1][c-1]);
                    if (c+1 < N)
                        best = Math.min(best, A[r+1][c+1]);
                    A[r][c] += best;
                }
            }
    
            int ans = Integer.MAX_VALUE;
            for (int x: A[0])
                ans = Math.min(ans, x);
            return ans;
        }
    }

#### [打家劫舍][Link 24] ####

方法一： 递归形式

public int rob1(int[] nums) {
        
        return dp1(nums, 0);
    }
    private int dp1(int[] nums, int start) {
        
        if (start >= nums.length) {
        
            return 0;
        }
        int res = Math.max(dp1(nums, start + 1), nums[start] + dp1(nums, start + 2));
        return res;
    }

方法二：备忘录+递归形式

private int[] memo;
    
    public int rob2(int[] nums) {
        
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return dp2(nums, 0);
    }
    private int dp2(int[] nums, int start) {
        
        if (start >= nums.length) {
        
            return 0;
        }
        if (memo[start] != -1) {
        
            return memo[start];
        }
        int res = Math.max(dp2(nums, start + 1), nums[start] + dp2(nums, start + 2));
        memo[start] = res;
        return res;
    }

方法三：动态规划

int rob3(int[] nums) {
        
        int n = nums.length;
        // dp[i] = x 表示：
        // 从第 i 间房子开始抢劫，最多能抢到的钱为 x
        // base case: dp[n] = 0
        int[] dp = new int[n + 2];
        for (int i = n - 1; i >= 0; i--) {
        
            dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
        }
        return dp[0];
    }

方法四：空间复杂度优化为O(1)

int rob4(int[] nums) {
        
        int n = nums.length;
        // 记录 dp[i+1] 和 dp[i+2]
        int dp_i_1 = 0, dp_i_2 = 0;
        // 记录 dp[i]
        int dp_i = 0;
        for (int i = n - 1; i >= 0; i--) {
        
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }

#### [打家劫舍 II][II 3] ####

public int rob(int[] nums) {
        
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robRange(nums, 0, n - 2), 
                        robRange(nums, 1, n - 1));
    }
    
    // 仅计算闭区间 [start,end] 的最优结果
    int robRange(int[] nums, int start, int end) {
        
        int n = nums.length;
        int dp_i_1 = 0, dp_i_2 = 0;
        int dp_i = 0;
        for (int i = end; i >= start; i--) {
        
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }

#### [打家劫舍 III][III] ####

方法一：

Map<TreeNode, Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        
        if (root == null) return 0;
        // 利用备忘录消除重叠子问题
        if (memo.containsKey(root)) 
            return memo.get(root);
        // 抢，然后去下下家
        int do_it = root.val
            + (root.left == null ? 
                0 : rob(root.left.left) + rob(root.left.right))
            + (root.right == null ? 
                0 : rob(root.right.left) + rob(root.right.right));
        // 不抢，然后去下家
        int not_do = rob(root.left) + rob(root.right);
    
        int res = Math.max(do_it, not_do);
        memo.put(root, res);
        return res;
    }

方法二：

int rob(TreeNode root) {
        
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }
    /* 返回一个大小为 2 的数组 arr
    arr[0] 表示不抢 root 的话，得到的最大钱数
    arr[1] 表示抢 root 的话，得到的最大钱数 */
    int[] dp(TreeNode root) {
        
        if (root == null)
            return new int[]{
        0, 0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        // 抢，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int not_rob = Math.max(left[0], left[1])
                    + Math.max(right[0], right[1]);
        return new int[]{
        not_rob, rob};
    }

#### [买卖股票的最佳时机][Link 25] ####

态转移方程总结一下：

base case：
    dp[-1][k][0] = dp[i][0][0] = 0
    dp[-1][k][1] = dp[i][0][1] = -infinity
    
    状态转移方程：
    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

读者可能会问，这个数组索引是 -1 怎么编程表示出来呢，负无穷怎么表示呢？这都是细节问题，有很多方法实现。现在完整的框架已经完成，下面开始具体化。

**三、秒杀题目**

**第一题，k = 1**

直接套状态转移方程，根据 base case，可以做一些化简：

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
    dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
                = max(dp[i-1][1][1], -prices[i])
    解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
    
    现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
    可以进行进一步化简去掉所有 k：
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], -prices[i])

直接写出代码：

int n = prices.length;
    int[][] dp = new int[n][2];
    for (int i = 0; i < n; i++) {
        
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    }
    return dp[n - 1][0];

显然 i = 0 时 dp\[i-1\] 是不合法的。这是因为我们没有对 i 的 base case 进行处理。可以这样处理：

for (int i = 0; i < n; i++) {
        
        if (i - 1 == -1) {
        
            dp[i][0] = 0;
            // 解释：
            //   dp[i][0] 
            // = max(dp[-1][0], dp[-1][1] + prices[i])
            // = max(0, -infinity + prices[i]) = 0
            dp[i][1] = -prices[i];
            //解释：
            //   dp[i][1] 
            // = max(dp[-1][1], dp[-1][0] - prices[i])
            // = max(-infinity, 0 - prices[i]) 
            // = -prices[i]
            continue;
        }
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    }
    return dp[n - 1][0];

第一题就解决了，但是这样处理 base case 很麻烦，而且注意一下状态转移方程，新状态只和相邻的一个状态有关，其实不用整个 dp 数组，只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):

// k == 1
    int maxProfit_k_1(int[] prices) {
        
        int n = prices.length;
        // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
        
            // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = max(dp[i-1][1], -prices[i])
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }

两种方式都是一样的，不过这种编程方法简洁很多。但是如果没有前面状态转移方程的引导，是肯定看不懂的。后续的题目，我主要写这种空间复杂度 O(1) 的解法。

**第二题，k = +infinity**

如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。可以这样改写框架：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
                = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
    
    我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

直接翻译成代码：

int maxProfit_k_inf(int[] prices) {
        
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
        
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

**第三题，k = +infinity with cooldown**

每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
    解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。

翻译成代码：

int maxProfit_with_cool(int[] prices) {
        
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        int dp_pre_0 = 0; // 代表 dp[i-2][0]
        for (int i = 0; i < n; i++) {
        
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }

**第四题，k = +infinity with fee**

每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
    解释：相当于买入股票的价格升高了。
    在第一个式子里减也是一样的，相当于卖出股票的价格减小了。

直接翻译成代码：

int maxProfit_with_fee(int[] prices, int fee) {
        
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
        
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
        }
        return dp_i_0;
    }

**第五题，k = 2**

k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。

这道题 k = 2 和后面要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出来了。我们直接写代码，边写边分析原因。

原始的动态转移方程，没有可化简的地方
    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

按照之前的代码，我们可能想当然这样写代码（错误的）：

int k = 2;
    int[][][] dp = new int[n][k + 1][2];
    for (int i = 0; i < n; i++)
        if (i - 1 == -1) {
         /* 处理一下 base case*/ }
        dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
    }
    return dp[n - 1][k][0];

为什么错误？我这不是照着状态转移方程写的吗？

还记得前面总结的「穷举框架」吗？就是说我们必须穷举所有状态。其实我们之前的解法，都在穷举所有状态，只是之前的题目中 k 都被化简掉了。比如说第一题，k = 1：

这道题由于没有消掉 k 的影响，所以必须要对 k 进行穷举：

int max_k = 2;
    int[][][] dp = new int[n][max_k + 1][2];
    for (int i = 0; i < n; i++) {
        
        for (int k = max_k; k >= 1; k--) {
        
            if (i - 1 == -1) {
         /*处理 base case */ }
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        }
    }
    // 穷举了 n × max_k × 2 个状态，正确。
    return dp[n - 1][max_k][0];

如果你不理解，可以返回第一点「穷举框架」重新阅读体会一下。

这里 k 取值范围比较小，所以可以不用 for 循环，直接把 k = 1 和 2 的情况全部列举出来也可以：

dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
    dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
    dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
    dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
    
    int maxProfit_k_2(int[] prices) {
        
        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
        for (int price : prices) {
        
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, -price);
        }
        return dp_i20;
    }

有状态转移方程和含义明确的变量名指导，相信你很容易看懂。其实我们可以故弄玄虚，把上述四个变量换成 a, b, c, d。这样当别人看到你的代码时就会大惊失色，对你肃然起敬。

**第六题，k = any integer**

有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。现在想想，交易次数 k 最多有多大呢？

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

直接把之前的代码重用：

int maxProfit_k_any(int max_k, int[] prices) {
        
        int n = prices.length;
        if (max_k > n / 2) 
            return maxProfit_k_inf(prices);
    
        int[][][] dp = new int[n][max_k + 1][2];
        for (int i = 0; i < n; i++) 
            for (int k = max_k; k >= 1; k--) {
        
                if (i - 1 == -1) {
         /* 处理 base case */ }
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);     
            }
        return dp[n - 1][max_k][0];
    }

至此，6 道题目通过一个状态转移方程全部解决。

[Link 1]: https://leetcode-cn.com/problems/coin-change/
[Link 2]: https://leetcode-cn.com/problems/triangle/
[Link 3]: https://leetcode-cn.com/problems/partition-equal-subset-sum/
[II]: https://leetcode-cn.com/problems/coin-change-2/
[Link 4]: https://leetcode-cn.com/problems/perfect-squares/
[Link 5]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[Link 6]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[Link 7]: https://leetcode-cn.com/problems/longest-palindromic-subsequence/
[Link 8]: https://leetcode-cn.com/problems/longest-common-subsequence/
[Link 9]: https://leetcode-cn.com/problems/count-different-palindromic-subsequences/
[Link 10]: https://leetcode-cn.com/problems/distinct-subsequences/
[II 1]: https://leetcode-cn.com/problems/distinct-subsequences-ii/
[Link 11]: https://leetcode-cn.com/problems/is-subsequence/
[Link 12]: https://leetcode-cn.com/problems/maximum-subarray/
[Link 13]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
[Link 14]: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
[Link 15]: https://leetcode-cn.com/problems/burst-balloons/
[Link 16]: https://leetcode-cn.com/problems/ones-and-zeroes/
[Link 17]: https://leetcode-cn.com/problems/climbing-stairs/
[Link 18]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/
[Link 19]: https://leetcode-cn.com/problems/edit-distance/
[Link 20]: https://leetcode-cn.com/problems/frog-jump/
[Link 21]: https://leetcode-cn.com/problems/super-egg-drop/
[Link 22]: https://leetcode-cn.com/problems/unique-paths/
[II 2]: https://leetcode-cn.com/problems/unique-paths-ii/
[Link 23]: https://leetcode-cn.com/problems/minimum-path-sum/
[Link 24]: https://leetcode-cn.com/problems/house-robber/
[II 3]: https://leetcode-cn.com/problems/house-robber-ii/
[III]: https://leetcode-cn.com/problems/house-robber-iii/
[Link 25]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/