动态规划

理论基础

动态规划中的每一个状态一定是由上一个状态推导出来的。

动态规划五部曲：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

动态规划如何debug：

确定状态转移公式（递推公式）是否有错？
打印dp数组，dp数组是否和推导的一致？

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1 2	`F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1`

给定 n ，请计算 F(n) 。

class Solution {
    
    public int fib(int n) {
        if(n < 2){
            return n;
        }
        int[] dp = new int [n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i < n + 1; i++){
            dp[i] = dp[i-1] + dp[i-2];
            System.out.println(dp[i]);
        }
        return dp[n];
    }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路：总结规律，发现后一步的可能等于当前步+上一步的可能性。其实又是一道斐波那契数列题。

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }
        int[] df = new int[n+1];
        df[1] = 1;
        df[2] = 2;
        for(int i = 3; i < n+1; i++){
            df[i] = df[i-1] + df[i-2];
        }
        return df[n];
    }
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

思路：主要是dp数组的含义无法确定，这个含义其实可以从题目中推测一下，例如计算的是到楼顶的最低花费，那么极有可能dp数组就是到每一个台阶的最低花费。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < dp.length; i++){
            dp[i] = dp[i-1] > dp[i-2] ? dp[i-2] + cost[i] : dp[i-1] + cost[i]; 
        }
        return dp[dp.length - 1] > dp[dp.length - 2] ? dp[dp.length - 2] : dp[dp.length - 1];
    }
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路：确定动态数组是每一步的可能路径数，然后递推公式是指，左边的加上上边的格子就行。初始化就是1，注意第一个是0。

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

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

思路：和上道题一样，dp数组是每个格子的可能路径数，规则也是一样，左边的加上上面的格子中的路径数量，注意如果该格子有障碍物就将其清零。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp = new int [obstacleGrid.length][obstacleGrid[0].length];
        if(obstacleGrid[0][0] != 0){
            return 0;
        }
        dp[0][0] = 1;
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                if(i == 0 && j == 0){
                    continue;
                }
                if(i == 0){
                    dp[i][j] = dp[i][j-1];
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];

    }
}

343. 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路：这个拆分其实可以用动规来解决，因为n的结果肯定是由前面的数来决定的。那么dp数组就是每个数字的最大拆分乘积，递推公式就是j*dp[i-j]，拆分拆分，肯定就是两个循环嵌套，取最大值保存到dp[i]就行。

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

思路：二叉树的问题一定和递归或者动态规划相关，这是树的特性决定的。该题主要难在递推公式的推导，确定了每个树的根节点就好办了。动态规划的推导公式往往都是规律的，列出n=4 5的情况推导就行了。

class Solution {
    public int numTrees(int n) {
        //初始化 dp 数组
        int[] dp = new int[n + 1];
        //初始化0个节点和1个节点的情况
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
                //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

背包问题之0-1背包

背包问题一般是指将具有特定价值的物品装入固定容量的背包中，并且求背包能背的最大价值。0-1背包是指物品数量只有一个或者只能装一次。用动态规划去解这类问题，是有模板的：

例如：

dp数组的确定

其中dp[i] [j] 代表任意选取0-i的物品的前提下，在背包重量j内的最大价值。
确定递推公式

dp[i] [j] 的推导有两个方向：
1. 在dp[i-1] [j]的基础上加value[i]的东西或者替换value[i] 的东西。
2. 与dp[i-1] [j]一样，不加东西。
1
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化

由于递推公式由dp[i-1] [j]递推而来，因此i要初始化，使用正序遍历。
1
2
3
for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; }

确定遍历顺序

一般是行先遍历，这里是物品先遍历。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

推导dp数组

这步一般是自己推导，用来debug。

public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

0-1背包的滚动数组解法

滚动数组其实就是把二维数组压缩成一维数组，节省空间，实际上时间复杂度还是O(n * m)。

具体原理就是将二维递推公式中的dp[i-1] [j]用dp[j]来表示，递归公式对比：

//二维数组
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
//滚动数组
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

注意：数组遍历顺序和二维数组有区别，具体是反过来的，因为初始化的过程就包含在递归过程中，因此正过来会导致初始化有影响。

//二维数组
for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
//滚动数组
 for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

416. 分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路：这题一开始想的是排序然后单指针划分区间，但在回文数组的情况下无法求解，这其实应该是一个经典的背包问题。可以将其看成背包容量为数组和的一半，用这个背包装数组里的数能不能恰好装满并且剩一个。

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++) {
            //这里是从后往前遍历，和（背包容量）必须要大于当前的num[i]（物品重量），否则就没必要更新了，因为装不下
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
           
            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

思路：

这题和上一题很像，本质就是分出一堆石头，使得这堆石头重量和尽量为总重量的一半，那么还是0-1背包。初始化为0，递推公式为dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); 要么不放、要么放。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        int target = sum >> 1;
        //初始化dp数组
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            //采用倒序
            for (int j = target; j >= stones[i]; j--) {
                //两种情况，要么放，要么不放
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
}

0-1 背包的组合问题

组合问题求解的就不是装到背包的最大值了，而是装到某个值有多少种方法。dp数组的定义也变成了装到某个值有多少种方法，因此递推公式就发生了变化，在组合问题中，公式往往都是这样：

1 2	`//后面的可能性等于前面的可能性相加，这里是运用了递归的思想 dp[j] += dp[j - nums[i]]；`

从递推公式可以看出，在初始化的时候dp[0] 一定要初始化为1，因为dp[0]是在公式中一切递推结果的起源，如果dp[0]是0的话，递推结果将都是0。

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
	    //如果target过大 sum将无法满足
        if ( target < 0 && sum < -target) return 0;
        //如果无法满足表达式，就返回0
        if ((target + sum) % 2 != 0) return 0;
        //背包容量就是和加target的一半，这样剩下的就是和减去target的一半，加起来刚好是target
        int size = (target + sum) / 2;
        //容量是可以小于0的
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

思路：这题应该是0-1背包问题，因为strs中每个元素只能选一次，而且求的是最大的子集长度。字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        //分别记录每个元素中1和0的数量
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    //这里是dp[weight-1]
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

背包问题之完全背包

完全背包和0-1背包的区别在于，完全背包中的东西可以多次放入。因此带来了几个特点：

完全背包的滚动数组可以背包、物品任意内外，而不是0-1背包的背包必须在外，物品必须在内。这是因为0-1的滚动数组必须倒序遍历。
完全背包内层循环是++，而非–，也就是得正序遍历。
如果求组合数就是外物内包，外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外包内物，外层for遍历背包，内层for循环遍历物品。

完全背包模板：

//先遍历物品，再遍历背包
private static void testCompletePack(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i < weight.length; i++){ // 遍历物品
        for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){
    int[] weight = {1, 3, 4};
    int[] value = {15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
        for (int j = 0; j < weight.length; j++){ // 遍历物品
            if (i - weight[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    for (int maxValue : dp){
        System.out.println(maxValue + "   ");
    }
}

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路：记住，求背包的组合问题，使用dp[j] += dp[j - coins[i]]的公式。记得初始化dp[0]为0。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        //这里是外物内包，求组合
        for(int i = 0; i < coins.length; i++){
            //这里直接从coins[i]开始，因为背包容量小于当前物品重量是没意义的，不会放进去
            for(int j = coins[i]; j <= amount; j++){
                //放进去后，当前的可能性由上一个背包决定
                dp[j] += dp[j - coins[i]];
            }      
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ

给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

思路：这题中，排序不同的序列被视作不同的组合，因此使用排列解法，外包内物。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //这里是外包内物，求排列，都从0开始
        for(int i = 0; i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                //如果能装下，就加一种可能性
                if (i - nums[j] >= 0){
                    dp[i] += dp[i - nums[j]];
                }
            }      
        }
        return dp[target];
    }
}

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

思路：咋一看像是贪心可以解的，但其实这里求的是刚好等于整数，而非超过整数。也就是有些amount数可能存在特定的几个因子数，是没办法用贪心来解的。那么就得用完全背包了，因为硬币可以重复取，需要注意求的是最小coins数，因此dp数组应该初始化为最大整数，除了dp[0]，其为0。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路：这题把物品看成完全平方数，背包看成n，就好解了。需要注意：求最少数量，dp还是初始化最大值，dp[0] = 0。这里的“物品”是小于n的所有完全平方数，从1开始；而背包容量则是从当前的“物品”容量开始，因为小于这个容量，就没必要讨论放不放；

class Solution {
    // 先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
	
        //当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                //if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                //}
		//不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。
            }
        }
        return dp[n];
    }
}

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路：可以多次放入，那么就是一个完全背包。s是背包，字典是物品，那么dp数组就是能否被字典拼接，是boolean类型的。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //dp数组定义是是否可以用字典单词拼接出当前字符串
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        //这种子串问题都要排列，也就是背包在外
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                int len = word.length();
                //背包容量大于当前字典单词才有意义
                //dp[i-len]为true，也就是如果要将当前字典放入，那么剩下的容量必须是可以被拼接的
                //同时剩下俩字符串必须相同
                if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

背包问题总结

416.分割等和子集1

确定dp数组（dp table）以及下标的含义，一般就是题目的问题。
确定递推公式
1. 背包最多能装多少：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
2. 装满有几种方法：dp[j] += dp[j - nums[i]] ；
3. 背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
4. 装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
dp数组如何初始化：这个看题目决定，一般是0或者1。

确定遍历顺序：

0-1背包的滚动数组是先遍历物品再遍历背包，并且第二层倒序遍历：

for(int i = 0; i < n; i++) {
    //
	for(int j = target; j >= nums[i]; j--){
        ......
    }
}

完全背包分不同情况：

求组合数就是先遍历物品再遍历背包：

for(int i = 0; i < coins.length; i++){
    for(int j = coins[i]; j <= amount; j++){
        ......
    }
}

求排列数就是先遍历背包再遍历物品：

for(int i = 0; i <= target; i++){
    for(int j = 0; j < nums.length; j++){
    ......
    }
}

举例推导dp数组：一般就是画图出来，与打印数组比较哪里出了问题。

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路：如何判断偷不偷这间？那就要看上一间偷了没，而上一间又得看上上间，这是典型的动态规划思路。动态数组的定义一般就是题目的问题，这里就是偷当前范围的房屋拿到的最高金额。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }else if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int [nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路：这里我是对比加油站，发现虽然成环了，但在哪里抢第一间根本不重要。那么问题就清晰了，确定有哪几种抢的范围。其实有两种，从第一间开始抢，从第二间开始抢。那么用两个dp数组就可以解决了，注意第一间开始抢，范围是length-2。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }else if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        int[] dp1 = new int [nums.length];
        int[] dp2 = new int [nums.length];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        dp2[0] = 0;
        dp2[1] = nums[1];
        for(int i = 2; i < nums.length - 1; i++){
            dp1[i] = Math.max(dp1[i-1], dp1[i-2] + nums[i]);
        }
        for(int i = 2; i < nums.length; i++){
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + nums[i]);
        }
        return Math.max(dp1[nums.length - 2], dp2[nums.length - 1]);
    }
}

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

思路：前一个房子偷不偷影响后一个房子偷不偷，这种是典型的动态规划。那么如何确定动态数组的含义？就是当前节点偷不偷拿到的最高金额，后续遍历到root根节点，然后判断偷根节点还是不偷。

class Solution {
    public int rob(TreeNode root) {
        int[] res = new int [2];
        //这里用一个递归函数搞定，实际上二叉树的题基本都涉及递归，因为这是遍历二叉树的方法
        res = robAction1(root);
        return Math.max(res[0], res[1]);
    }
	
    int[] robAction1(TreeNode root) {
        //每次递归都新建一个dp数组记录当前节点偷不偷的金额
        int res[] = new int[2];
        //递归终止条件
        if (root == null)
            return res;
		//这里是典型的后序遍历
        int[] left = robAction1(root.left);
        int[] right = robAction1(root.right);
		//res[0]是不偷，那么就取决于左右子节点偷的最大金额
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //res[1]是偷，那么就是当前节点的价值加上左右子节点不偷的最大金额
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：这题一看只能卖一次，自然就想到了取左边的最小值，然后不断更新卖出的结果，在结果中取最大值。这就是贪心。动态规划要抽象很多，在当前操作有持有卖出两种状态，将这个状态记录到滚动数组就行。

贪心

class Solution {
    public int maxProfit(int[] prices) {
        // 找到一个最小的购入点
        int low = Integer.MAX_VALUE;
        // res不断更新，直到数组循环完毕
        int res = 0;
        for(int i = 0; i < prices.length; i++){
            low = Math.min(prices[i], low);
            res = Math.max(prices[i] - low, res);
        }
        return res;
    }
}

动态规划

class Solution {
  public int maxProfit(int[] prices) {
    int[] dp = new int[2];
    // 记录一次交易，一次交易有买入卖出两种状态
    // 0代表持有，1代表卖出
    dp[0] = -prices[0];
    dp[1] = 0;
    // 可以参考斐波那契问题的优化方式
    // 我们从 i=1 开始遍历数组，一共有 prices.length 天，
    // 所以是 i<=prices.length
    for (int i = 1; i <= prices.length; i++) {
      // 前一天持有；或当天买入
      dp[0] = Math.max(dp[0], -prices[i - 1]);
      // 如果 dp[0] 被更新，那么 dp[1] 肯定会被更新为正数的 dp[1]
      // 而不是 dp[0]+prices[i-1]==0 的0，
      // 所以这里使用会改变的dp[0]也是可以的
      // 当然 dp[1] 初始值为 0 ，被更新成 0 也没影响
      // 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行
      dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
    }
    return dp[1];
  }
}

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

思路：这题可以同一天出售，肯定就是贪心，有赚的全买卖；动态规划思路和上一题差不多。

//1. 贪心
class Solution {
    public int maxProfit(int[] prices) {
      //这题用贪心的思路，如果后一天的价格比前一天大，就可以买
      //但注意只能持有一股，也就是买出和卖出是间隔的
      int maxProfit = 0; 
      int currentProfit = 0;
      if(prices.length == 1){
          return 0;
      }
      for(int i = 1; i < prices.length; i++){
          currentProfit = prices[i] - prices[i-1];
          if(currentProfit > 0){
            maxProfit += currentProfit;
          }
      }
      return maxProfit;
    }
}

//2. 动态规划
class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[2];
        // 0表示持有，1表示卖出
        dp[0] = -prices[0];
        dp[1] = 0;
        for(int i = 1; i <= prices.length; i++){
            // 前一天持有; 既然不限制交易次数，那么再次买股票时，要加上之前的收益
            dp[0] = Math.max(dp[0], dp[1] - prices[i-1]);
            // 前一天卖出; 或当天卖出，当天卖出，得先持有
            dp[1] = Math.max(dp[1], dp[0] + prices[i-1]);
        }
        return dp[1];
    }
}

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：这个思路和上面两题是一样的，就是状态多了几种。这里可以做一个优化，直接拿变量替换dp数组，因为递推公式只涉及到了前一个元素的状态，因此实际上不需要数组保存前一个以前的状态。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }

        return dp[len - 1][4];
    }
}

//空间优化
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 4 种状态:
         * 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int dp1 = -prices[0];
        int dp2 = 0;
        int dp3 = -prices[0];
        int dp4 = 0;
        for (int i = 1; i < len; i++) {
            dp1 = Math.max(dp1, -prices[i]);
            dp2 = Math.max(dp2, dp1 + prices[i]);
            dp3 = Math.max(dp3, dp2 - prices[i]);
            dp4 = Math.max(dp4, dp3 + prices[i]);
        }
        return dp4;
    }
}

188. 买卖股票的最佳时机 IV

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：这和上一题的思路一模一样，就是把空间优化里的四个dp数换成了长度为2k的数组。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        int len = 2 * k;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            if(i % 2 == 0){
                dp[i] = -prices[0];
            }
        }
        for(int i = 1; i < prices.length; i++){
            for(int j = 0; j < len; j++){
                if(j == 0){
                    dp[j] = Math.max(dp[j], -prices[i]);
                }else if(j % 2 == 0){
                    dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
                }else{
                    dp[j] = Math.max(dp[j], dp[j-1] + prices[i]);
                }
            }
        }
        return dp[len-1];
    }
}

309. 买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：这题卡在了如何跳出冷冻期，其实很简单，使用临时变量在递推公式上面保留上一个变量的值。

class Solution {
    public int maxProfit(int[] prices) {
        //分别表示：
        //dp[0]持有股票，可能是之前持有，也可能是今天买入（冰冻期后一天立即买入，或者过几天再买）
        //dp[1]保持股票卖出的状态，可能是之前就是卖出的状态，或者两天前卖出的，刚过冷冻期
        //dp[2]今天卖出股票
        //dp[3]冷冻期
        int[] dp=new int[4];

        dp[0] = -prices[0];
        dp[1] = 0;
        for(int i = 1; i < prices.length; i++){
          	// 使用临时变量来保存dp[0], dp[2]
            // 因为马上dp[0]和dp[2]的数据都会变 
            int temp = dp[0];
            int temp1 = dp[2];
            dp[0] = Math.max(dp[0], Math.max(dp[3], dp[1]) - prices[i]);
            dp[1] = Math.max(dp[1], dp[3]);
            dp[2] = temp + prices[i];
            dp[3] = temp1;
        }
        return Math.max(dp[3],Math.max(dp[1],dp[2]));
    }
}

714. 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

思路：这题就是不能当天买入卖出，同时还要收手续费，注意用临时变量避开当天买入卖出就行。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if(prices.length == 1){
            return 0;
        }
        int dp1 = -prices[0];
        int dp2 = 0;
        for(int i = 1; i < prices.length; i++){
            int temp = dp1;
            //持有股票：之前就持有;或者当天刚买入，也就是上一天没有持有股票
            dp1 = Math.max(dp1, dp2 - prices[i]);
            //不持有股票：之前就不持有;或者当天刚卖出，也就是上一天持有股票
            dp2 = Math.max(dp2, temp + prices[i] - fee);
        }
        return dp2;
    }
}

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路：这题主要没想到可以用两个for循环，O(n)的复杂度。只要第二个循环不断比较0-i范围内的dp数组，决定要不要加就行。

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

优化：看看能不能在第二个循环实现二分搜索。重新定义dp数组，dp[j]即为长度j+1的递增子序列最后一个元素，然后nums[i]与dp[j]对比，这个过程可以二分搜索，如果小于就更新这个dp[j]，否则就更新在dp[i]上，最后返回最后一个dp[i]就行。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int [nums.length];
        int res = 0;
        for(int num : nums){
            //i j分别是最长子序列的左右边界
            int i = 0;
            int j = res;
            while(i < j){
                //这里使用了二分搜索，找到比num大的tails[m]
                int m = (i + j) / 2;
                if(tails[m] < num){
                    i = m + 1;
                }else{
                    j = m;
                }
            }
            //替换比num大的tails[m]，或者更新一个新的子序列
            tails[i] = num;
            //右边界没有更新，也就是当前最长子序列的最后一位比num小
            if(res == j){
                res++;
            }
        }
        return res;

    }
}

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

思路：首先就想到贪心，后一个大于前一个就加一，否则就归一，再拿一个变量记录最大的length；第二种解法是动态规划，dp[i]是最长连续递增序列，如果num[i+1]大于nums[i]，那么就更新，否则就不更新。

//贪心
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 1){
            return 1;
        }
        int res = 1;
        int length = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > nums[i-1]){
                length++;
            }else{
                length = 1;
            }
            res = length > res ? length : res;
        }
        return res;
    }
}

//动态规划
class solution {
    public static int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int res = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                dp[i + 1] = dp[i] + 1;
            }
            res = res > dp[i + 1] ? res : dp[i + 1];
        }
        return res;
}

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路：这题用动态规划来解决，核心思想是使用dp数组记录遍历过程中的子数组长度，再用一个变量保存最大值。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int [] dp = new int[nums2.length + 1];
        int res = 0;
        for(int i = 0; i < nums1.length; i++){
            //这里使用滚动数组，但递推公式用到了前面的数据，所以从后遍历
            for(int j = nums2.length-1; j >= 0; j--){
                if(nums1[i] == nums2[j]){
                    dp[j + 1] = dp[j] + 1;
                }else{
                    dp[j + 1] = 0;
                }
                res = res > dp[j+1] ? res : dp[j+1];
            }
        }
        return res;
    }
}

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路：子序列问题是典型的动态规划题，本题的主要重点就是使用一个临时变量来储存dp[j+1]，然后使用pre来储存上一个变量。如果这题看不懂，就看下一题，有二维数组，比较好理解。

//二维数组版本
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1]; 
        for (int i = 1 ; i <= text1.length() ; i++) {
            char char1 = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j++) {
                char char2 = text2.charAt(j - 1);
                if (char1 == char2) { 
                    //之所以是dp[i-1][j-1]，是因为两个数组同时截去最后一位才有意义，才能加一
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //否则就是每个数组分别截去最后一位，取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

//滚动数组版本
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[] dp = new int[text2.length() + 1];
        for (int i = 0; i < text1.length(); i++) {
            //这里的pre对应的是dp[i-1][j-1]
            int prev = 0;
            for (int j = 0; j < text2.length(); j++) {
                int temp = dp[j + 1];
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[j + 1] = prev + 1;
                } else {
                    dp[j + 1] = Math.max(dp[j], dp[j + 1]);
                }
                prev = temp;
            }
        }
        return dp[text2.length()];
    }
}

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

思路：这题一看确实没什么思路，仔细一想，这不就是最长公共子序列吗！

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
}

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

思路：核心思想是判断当前元素该不该加入前一个连续子数组，这里是判断当前元素和前一个连续子数组的和哪个大。

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

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

思路：这题显而易见可以用双指针，用筛漏斗的方式，O(n)即可得解。而子序列又是动态规划的经典题目，因此引入动态规划，作为一个经典的模板。

//双指针解法
class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0){
            return true;
        }
        int start = 0;
        boolean flag = false;
        for(int i = 0; i < s.length(); i++){
            for(int j = start; j < t.length(); j++){
                if(s.charAt(i) == t.charAt(j)){
                    if(i == s.length() - 1){
                        return true;
                    }
                    flag = true;
                    start = j + 1;
                    break;
                }
            }
            if(!flag){
                return false;
            }
            flag = false;
        }
        return false;
    }
}

//动态规划解法
class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }
    }
}

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对$10^9$ + 7 取模。

思路：子序列，这应该是一道动态规划，出现的个数就是递推公式的关键。主要是t不一定用当前的s匹配，也可以少上一个字母。

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
		//dp的长度比数组长度大一，也就是dp[i]代表的实践上是s[i-1]
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    //这里dp有两个来源，一个是当前的s[i-1]，另一个是s[i-2]
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

583. 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

思路：这题一看，只删除的话那不就妥妥的最长公共子序列吗！

class Solution {
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word2.length() + 1];
        for(int i = 0; i < word1.length(); i++){
            int prev = 0;
            for(int j = 0; j < word2.length(); j++){
                int temp = dp[j + 1];
                if(word1.charAt(i) == word2.charAt(j)){
                    dp[j + 1] = prev + 1;
                }else{
                    dp[j + 1] = Math.max(dp[j], dp[j + 1]);
                }
                prev = temp;
            }
        }
        return word1.length() + word2.length() - 2*dp[word2.length()];

    }
}

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

思路：这题就不是完全的最长公共子序列了，但思路是差不多的，多了删除word2和替换word1这个选项。

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 初始化，与空字符串比较，全部删除，因此操作数是i和j
    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 (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                //一样就不操作
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                //分别对应替换元素，删除word1元素，删除word2元素
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[m][n];
}

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

思路：回文相关的，首先想到双指针，使用中心扩散法。连续子序列，想到了动态规划，关键是状态转移方程的推导，这里其实也是中心扩散的思想，因为s[i,j]是不是回文序列，靠s[i]是否等于s[j]，同时还要看s[i+1] [j-1]是不是回文序列。

//动态规划
class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1) { // 一个或者两个字符
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 三个及以上字符
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}

//双指针
class Solution {
    public int countSubstrings(String s) {
        int len, ans = 0;
        if (s == null || (len = s.length()) < 1) return 0;
        //总共有2 * len - 1个中心点
        for (int i = 0; i < 2 * len - 1; i++) {
            //通过遍历每个回文中心，向两边扩散，并判断是否回文字串
            //有两种情况，left == right，right = left + 1，这两种回文中心是不一样的
            int left = i / 2, right = left + i % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                //如果当前是一个回文串，则记录数量
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }
}

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

思路：子序列，应该是动态规划，要找到回文的，思路和上一题差不多。但注意dp数组记录的是最长回文子序列的长度。而状态转移公式中，dp[i] [j]是由删去左边或右边的元素推导出的。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        if(len == 1){
            return 1;
        }
        int[][] dp = new int [len + 1][len + 1];
        int res = 0;
        for(int i = len - 1; i >= 0; i--){
            //初始化为1，因为遍历中把只有一个字符串的情况省略了
            dp[i][i] = 1;
            for(int j = i + 1; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                    //相等的情况下，s[i,j]的最大值等于s[i-1][j-1]，即截去两边的元素
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    //不相等，就分别截去两端的元素，取最大值
                    dp[i][j] = Math.max(Math.max(dp[i+1][j], dp[i][j-1]), dp[i][j]);
                }
            }
        }
        return dp[0][len-1];
    }
}

算法

#算法 #刷题

动态规划

https://wengerblogs.me/2025/05/13/动态规划/

Author

Wenger

Posted on

May 13, 2025

Licensed under

Hot100刷题 Previous

回溯算法 Next