动态规划

涉及动态规划的题，解法三部曲

1.定义dp数组 明确dp数组含义

2.找到状态专业方程

3.具体编码

子序列问题

这里列举几道leetcode子序列的题（中等和困难难度的）

300. 最长递增子序列

题目描述：

编码：

import java.util.Arrays;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int dp[]=new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    //  核心代码
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        Arrays.sort(dp);
        return dp[n-1]; }
}

1143. 最长公共子序列

题目描述：

编码：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
             int n1=text1.length();
             int n2=text2.length();
             //dp[i][j] 表示text1[0...i-1],text2[0...j-1]的最长子序列长度
            int [][]dp=new int [n2+1][n1+1];
             for(int i=1;i<=n2;i++){
                 for(int j=1;j<=n1;j++){
                     if(text2.charAt(i-1)==text1.charAt(j-1)){
                         dp[i][j]=dp[i-1][j-1]+1;
                     }else{
                         dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                     }
                 }
             }

   return dp[n2][n1]; }
}

72. 编辑距离

题目描述：

编码：

class Solution {
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // dp[i][j]:返回nums1[0..i-1]和nums2[0...j-1]的最少操作数
        int[][] dp = new int[m + 1][n + 1];
        // base case 有一个字符串为空
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;
        // 自底向上求解
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(
                            dp[i][j-1] + 1, //   删除
                            dp[i - 1][j - 1] + 1, //替换
                            dp[i-1][j] + 1//插入
                    );
        // 储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

516. 最长回文子序列

题目描述：

编码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        //dp[i][j]表示s[i...j]的最长回文子序列
        int [][]dp=new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=2+dp[i+1][j-1];
                }else {
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];  }
}

动态规划解决子序列算法问题总结

解决子序列问题有两种模板，相关问题只要往这两种思路上想，十拿九稳。

一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符嘛，没啥可问的。一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧。

我们说的两种思路模板，就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。

第一种思路模板是一个一维的 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 数组的定义是：

在子数组**array[0..i]**中，以array[i]结尾的目标子序列（最长递增子序列）的长度是**dp[i]**。

第二种思路模板是一个二维的 dp 数组：

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

涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：

在子数组**arr1[0..i]**和子数组**arr2[0..j]**中，我们要求的子序列（最长公共子序列和编辑距离）长度为**dp[i][j]**。

只涉及一个字符串/数组时，dp 数组的含义如下：

在子数组**array[i..j]**中，我们要求的子序列（最长回文子序列）的长度为**dp[i][j]**。

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] = 最值(...)
    }
}

背包问题：

零钱兑换

题目描述：

解法：

class Solution {
    int []memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        // dp 数组全都初始化为特殊值
        Arrays.fill(memo,-66);
        return dp(coins, amount);
    }

    public int dp(int []coins,int amount){
        int res=Integer.MAX_VALUE;
        if(amount<0){
            return -1;
        }
        if(amount==0){
            return 0;
        }
        // 查备忘录，防止重复计算
        if(memo[amount]!=-66){
            return memo[amount];
        }
        for(int i=0;i<coins.length;i++){
            int sum=dp(coins,amount-coins[i]);
            if(sum<0){
            }else {
                // 在子问题中选择最优解，然后加一
                res=Math.min(sum+1,res);
            }
        }
        // 把计算结果存入备忘录
        memo[amount]=res==Integer.MAX_VALUE?-1:res;
        return memo[amount];  }
}

零钱兑换 II

题目描述：

解法：

class Solution {
    public int change(int amount, int[] coins) {
        // 定义dp[m][n] 表示前m种选择凑成n元的组合总数
        int m=coins.length;
        int dp[][]=new int[m+1][amount+1];
        //base case
        for(int i=0;i<=m;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=amount;j++){
                //根据dp数组的定义 注意是i-1
                if(j>=coins[i-1]){
                    dp[i][j]=dp[i][j-coins[i-1]]+dp[i-1][j];
                }else {
                    dp[i][j]=dp[i-1][j];
                }

            }
        }
        return dp[m][amount]; }
}

分割等和子集

解法：

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        //do[m][n]表示 对应前m个数，正好可以凑成数字为n
        int sum=0;
        int n=nums.length;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }

        //基数直接pass掉
        if(sum%2!=0){
            return false;
        }sum=sum/2;
        boolean dp[][]=new boolean[n][sum+1];
        //base case
        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){
                    //选不了
                    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-1][sum];  }
}