代码随想录算法训练营第46+天

今日任务

46+0：part08 ● 多重背包

链接：https://docs.qq.com/doc/DUHhuT2RTTEtBeGhX (opens in a new tab)

46+1：part09 ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

链接：https://docs.qq.com/doc/DUGd5ZkNZS1NsYkFk (opens in a new tab)

46+1：part10 ● 121. 买卖股票的最佳时机 ● 122. 买卖股票的最佳时机II ● 123. 买卖股票的最佳时机III ● 188. 买卖股票的最佳时机IV ● 309. 最佳买卖股票时机含冷冻期 ● 714. 买卖股票的最佳时机含手续费

链接：https://docs.qq.com/doc/DUFhzV29ZSEtFVkto (opens in a new tab)

● 300.最长递增子序列 ● 674.最长连续递增序列 ● 718.最长重复子数组 ● 1143.最长公共子序列

● 1035.不相交的线 ● 53. 最大子序和 ● 392.判断子序列 ● 115.不同的子序列 ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 647. 回文子串 ● 516.最长回文子序列 ● ●

● ● ●

多重背包

多重背包和01背包是非常像的，

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

198.打家劫舍

自己想法

每走到一个位置，可以选择偷或者不偷，偷的话，那么就是dp[i] = dp[i-2] + nums[i]；不偷的话，那么就是dp[i] = dp[i-1]，注意这里不代表一定会偷i-1。

dp[i]表示走到i位置时的最大值，dp[i] = max(dp[i-1], dp[i-2] + nums[i])

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        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(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

213.打家劫舍II

题解想法

因为是环形，所以可以分成两种情况：

不偷第一个房子，那么就是[1, n]的最大值
不偷最后一个房子，那么就是[0, n-1]的最大值

两者取最大即可。

思考：有没有可能不偷第一个房子时，后续[1]和[n]的房子也都没被偷，此时偷第一个房子必然可以更多？

如：1, 1, 8, 1, 9, 1，不偷第一个房子，偷8和9，但此时因为1和1都没被偷，所以偷第一个房子可以更多。

答：这种情况会在[0, n-1]中被考虑到。

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

337.打家劫舍 III

题解想法

动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形dp的入门题目，因为是在树上进行状态转移。

树的遍历是后序遍历，因为需要先知道左右子树的状态。

思考：为什么要用两个数来记录状态？

答：回顾打家劫舍和打家劫舍II，可以通过下标访问到dp[i - 2]和dp[i - 1]，那么在树的递归中只能拿到上一层的值，即只能访问到dp[i - 1]，也就是说只能判断不抢i节点的情况，所以抢不抢本节点的判断只能交由上级判断，所以需要两个数来记录状态。

class Solution {
    int max = 0;
    public int rob(TreeNode root) {
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }
    // 返回值：第一个数表示不偷root时的最大， 第二个数表示偷root时的最大
    private int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};
 
        int[] ans_left = dfs(root.left);
        int[] ans_right = dfs(root.right);
        
        // 不偷root：
        int skip_root = Math.max(ans_left[1], ans_left[0]) + Math.max(ans_right[1], ans_right[0]);
        
        // 偷root：root.val + 两边都不偷
        int rob_root = root.val + ans_left[0] + ans_right[0];
 
        return new int[]{skip_root, rob_root};
    }
}

超时的写法：

暴力递归，会有很多重复计算。

class Solution {
    public int rob(TreeNode root) {
        return dfs(root);
    }
    private int dfs(TreeNode root) {
        if (root == null) return 0;
 
        // 偷root：root.val + 
        int rob_root = root.val;
        if (root.left != null) rob_root = rob_root + dfs(root.left.left) + dfs(root.left.right);
        if (root.right != null) rob_root = rob_root + dfs(root.right.left) + dfs(root.right.right);
        
        // 不偷root：dfs(root.left) + dfs(root.right);
        int skip_root = dfs(root.left) + dfs(root.right);
 
        return Math.max(rob_root, skip_root);
    }
}

121. 买卖股票的最佳时机

限制只能买卖一次

自己想法

贪心，找最左的最小，然后找最大的差值。

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }
}

题解想法

动规：

dp[i][0]代表第i天持有股票的最大收益，dp[i][1]代表第i天不持有股票的最大收益。

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，因为只能买入一次，所以所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

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

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

自己想法

曾经使用贪心 (opens in a new tab)，

今天使用动规。

与上题的区别是，这里可以买卖多次。所以第i天买入股票，体现在代码上，所得现金是上一天没有持有股票的现金减去今天的股价：dp[i - 1][1] - prices[i]

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; 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], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

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

限制只能买卖两次

题解想法+自己想法

dp数组保存四个状态：

dp[i][0]：第i天第一次持有股票

dp[i][1]：第i天第一次不持有股票（包括没买过和买过一次卖掉）

dp[i][2]：第i天第二次持有股票

dp[i][3]：第i天第二次不持有股票（买过两次卖掉）

class Solution {
    // dp[i][0]：第i天第一次持有股票
    // dp[i][1]：第i天第一次不持有股票（包括没买过和买过一次卖掉）
    // dp[i][2]：第i天第二次持有股票
    // dp[i][3]：第i天第二次不持有股票（买过两次卖掉）
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + 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]);
        }
        return dp[prices.length - 1][3];
    }
}

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

自己想法

上一题的扩展，可以买卖k次。

dp数组保存2k个状态

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

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

题解想法+自己想法

dp数组保存四个状态：

dp[i][0]：第i天持有股票，也可能是保持有股票的状态

dp[i][1]：第i天刚卖（不持有股票）

dp[i][2]：第i天卖后第二天，冷冻（不持有股票）

dp[i][3]：第i天可以买入了，但依旧（不持有股票）

状态转移只需看指向这个状态的箭头即可。

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        dp[0][0] = -prices[0];  // 持有
        dp[0][1] = 0;           // 刚卖（不持有)
        dp[0][2] = 0;           // 卖后第二天，冷冻（不持有）
        dp[0][3] = 0;           // 不持有
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][3] - prices[i]), dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = Math.max(dp[i - 1][2], dp[i - 1][3]);
        }
        return Math.max(Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]), dp[prices.length - 1][3]);
    }
}

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

自己想法

只需在122. 买卖股票的最佳时机II的基础上减去手续费即可。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; 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], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.length - 1][1];
    }
}

300.最长递增子序列

题解想法

dp[i]表示以nums[i]结尾的最长递增子序列的长度。

需要两层循环，第一层遍历nums，第二层遍历i之前的所有元素，找到最大的dp[j] + 1。

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

674.最长连续递增序列

自己想法

本题要求连续，

dp[i]依旧表示以nums[i]结尾的最长连续递增序列的长度。

需要一层循环，遍历一次即可

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

718.最长重复（公共）子数组

题解想法

子数组，其实就是连续子序列，要求连续。

dp[i][j]表示以nums1[i]结尾和以nums2[j]结尾的最长公共子数组的长度。

两层循环，第一层遍历nums1，第二层遍历nums2，找到最大的dp[i][j]。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int ans = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (nums1[0] == nums2[i]) dp[0][i] = 1;
            if (dp[0][i] > ans) ans = dp[0][i];
        }
        for (int i = 0; i < nums1.length; i++) {
            if (nums2[0] == nums1[i]) dp[i][0] = 1;
            if (dp[i][0] > ans) ans = dp[i][0];
        }
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > ans) ans = dp[i][j];
            }
        }
        return ans;
    }
}

1143.最长公共子序列

以上四道题目的联系与区别是：

题目	数组数量	dp数组维度	连续性要求	循环层数	备注
674.最长连续递增序列	一个数组	1	连续	1
300.最长递增子序列	一个数组	1	不连续	2	相当于674的拓展，实现起来更复杂
718.最长重复子数组	两个数组	2	连续	2
1143.最长公共子序列	两个数组	2	不连续	4优化为2	相当于718的拓展，实现起来更复杂

自己想法

dp[i][j]表示以text1[i]和text2[j]结尾的最长公共子序列的长度。

较为暴力的解法是四层循环，第一层遍历text1，第二层遍历text2，目的是确定dp[i][j]；而确定dp[i][j]还需要第三、四层循环（m,n）遍历dp[0][0]到dp[i-1][j-1]的最大。

然而这样会超时。（如注释掉的代码的写法）

注意到第三、四层循环内其实是有重复计算的，所以可以再次使用动规来优化。

使用max_dp[i][j]来记录dp[i][j]包络区域的最大值（不包括i行j列）。

max_dp[i][j]则等于max_dp[i - 1][j], max_dp[i][j - 1]和dp[i - 1][j - 1]的最大值。

最终简化为两层循环，第一层遍历text1，第二层遍历text2，找到最大的dp[i][j]。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        int[][] max_dp = new int[text1.length()][text2.length()];  // 记录dp[i][j]包络区域最大值（不包括i行j列）
        int ans = 0;
        for (int i = 0; i < text2.length(); i++) {
            if (text1.charAt(0) == text2.charAt(i)) dp[0][i] = 1;
            if (dp[0][i] > ans) ans = dp[0][i];
        }
        for (int i = 0; i < text1.length(); i++) {
            if (text2.charAt(0) == text1.charAt(i)) dp[i][0] = 1;
            if (dp[i][0] > ans) ans = dp[i][0];
        }
        for (int i = 1; i < text1.length(); i++) {
            for (int j = 1; j < text2.length(); j++) {
                max_dp[i][j] = Math.max(Math.max(max_dp[i - 1][j], max_dp[i][j - 1]), dp[i - 1][j - 1]);
 
                if (text1.charAt(i) == text2.charAt(j)) {
                    // for (int m = 0; m < i; m++) {
                    //     for (int n = 0; n < j; n++) {
                    //         dp[i][j] = Math.max(dp[i][j], dp[m][n] + 1);
                    //     }
                    // }
 
                    dp[i][j] = max_dp[i][j] + 1;
                }
                if (dp[i][j] > ans) ans = dp[i][j];
            }
        }
        return ans;
    }
}

题解想法

其实不用像我一样再使用max_dp数组，直接修改dp及其递推公式即可。

dp[i][j]表示text1[0, i]和text2[0, j]的最长公共子序列的长度。而不是以text1[i]和text2[j]结尾的最长公共子序列的长度。

递推公式主要就是两大情况： text1[i] 与 text2[j]相同，text1[i] 与 text2[j]不相同

如果text1[i] 与 text2[j]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i] 与 text2[j]不相同，那就看看text1[0, i - 1]与text2[0, j] 的最长公共子序列和 text1[0, i]与text2[0, j - 1]的最长公共子序列，取最大的。

但是这里初始化比较麻烦...

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()][text2.length()];
        int ans = 0;
        if (text1.charAt(0) == text2.charAt(0)) {
            dp[0][0] = 1;
            ans = 1;
        }
        for (int i = 1; i < text2.length(); i++) {
            if (text1.charAt(0) == text2.charAt(i)) dp[0][i] = 1;
            else dp[0][i] = dp[0][i - 1];
            if (dp[0][i] > ans) ans = dp[0][i];
        }
        for (int i = 1; i < text1.length(); i++) {
            if (text2.charAt(0) == text1.charAt(i)) dp[i][0] = 1;
            else dp[i][0] = dp[i - 1][0];
            if (dp[i][0] > ans) ans = dp[i][0];
        }
        for (int i = 1; i < text1.length(); i++) {
            for (int j = 1; j < text2.length(); j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(Math.max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
                if (dp[i][j] > ans) ans = dp[i][j];
            }
        }
        return ans;
    }
}

1035.不相交的线

自己想法

dp[i][j]表示nums1[0, i]和nums2[0, j]包络范围的最大值

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        if (nums1[0] == nums2[0]) {
            dp[0][0] = 1;
        }
        for (int i = 1; i < nums2.length; i++) {
            if (nums1[0] == nums2[i]) dp[0][i] = 1;
            else dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i < nums1.length; i++) {
            if (nums2[0] == nums1[i]) dp[i][0] = 1;
            else dp[i][0] = dp[i - 1][0];
        }
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                dp[i][j] = Math.max(Math.max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                if (nums1[i] == nums2[j]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                // 上面两句可以简化一下：
                // dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                // if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            }
        }
        return dp[nums1.length - 1][nums2.length - 1];
    }
}

题解想法

本题实际上是求两个数组的最长公共子序列：1143.最长公共子序列

53. 最大子序和

本题曾经使用贪心 (opens in a new tab) ，今天使用动规。

自己想法

dp[i]表示以nums[i]结尾的最大子序和。

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

392.判断子序列

自己想法

dp[i][j]表示s[0, i]和t[0, j]的最长公共子序列的长度。

与1143.最长公共子序列相比，本题在s.charAt(i) != t.charAt(j) 时，不能再去找最大值，只能是dp[i][j] = dp[i][j - 1]，意思是s数组不能减。

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

115.不同的子序列

自己想法

dp[i][j]表示从s[0, i-1]中找t[0, j-1]的个数。

本题写之前就感觉到初始化可能会麻烦，所以采取从718. 最长重复子数组开始题解推荐的大一圈的dp数组，维度是[s.length() + 1][t.length() + 1]。

同样由于t数组不能减，所以当s.charAt(i) == t.charAt(j) 时， dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。反之，dp[i][j] = dp[i - 1][j]。

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(); i++) dp[i][0] = 1;
        // dp[0][0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

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

自己想法

本题与1143.最长公共子序列类似，逆向思考。只是最后返回的是两个字符串的长度减去最长公共子序列的长度的2倍。

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(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 word1.length() + word2.length() - dp[word1.length()][word2.length()] * 2;
    }
}

题解想法

当然也可以正向思考链接 (opens in a new tab)：

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

确定递推公式

当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
- 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
- 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
- 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
那最后当然是取最小值，dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

dp[0][j]的同理。

72.编辑距离

自己想法

dp[i][j]：word1从第0到第i字符转换成 word2从第0到第j字符所需最少次数

tips：表面上word2是不能动的，但实际上word1的插入操作和word2的删除操作是等价的。所以递推公式中，插入的情况：dp[i][j - 1] + 1

class Solution {
    public int minDistance(String word1, String word2) {
        // dp[i][j]：word1从第0到第i字符 转换成 word2从第0到第j字符所需最少次数
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 初始化：word1长度为0时，word1要转换成word2，那么word1需要插入j个字符
        //        word2长度为0时，word1要转换成word2，那么word1需要删除i个字符
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;  
        }for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;  
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    // 插入的情况：dp[i][j - 1] + 1
                    // 删除的情况：dp[i - 1][j] + 1
                    // 替换的情况：dp[i - 1][j - 1] + 1
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1), dp[i - 1][j] + 1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

647. 回文子串

自己想法

dp[i][j]表示s[i, j]是否是回文串。

递推公式：

当s[i] == s[j]时，

如果i和j之间的字符串是回文串，那么s[i, j]也是回文串。
- i和j差1时，dp[i][j] = true
- 否则，dp[i][j] = dp[i + 1][j - 1]
当s[i] != s[j]时，s[i, j]不是回文串。

遍历顺序：从下往上，左右没关系，我这里是从右往左。

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int i = s.length() - 2; i >= 0; i--) {
            for (int j = s.length() - 1; j > i; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    if ((i + 1) == j) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                else dp[i][j] = false;
            }
        }
        int count = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

题解想法

中心扩展法：

确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况。

一个元素可以作为中心点，两个元素也可以作为中心点。

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            ans += expand(i, i, s);      // 一个元素作为中心点
            ans += expand(i, i + 1, s);  // 两个元素作为中心点
        }
        ans += expand(s.length() - 1, s.length() - 1, s);
        return ans;
    }
    private int expand(int i, int j, String s) {
        int count = 0;
        while (i >= 0 && j <= s.length() - 1 && s.charAt(i) == s.charAt(j)) {
            count++;
            i--;
            j++;
        }
        return count;
    }
}

516.最长回文子序列

自己想法

dp[i][j]表示s[i, j]的最长回文子序列的长度。

递推公式：

当s[i] == s[j]时，如果i和j之间的字符串是回文串，那么s[i, j]也是回文串。
- i和j差1时，dp[i][j] = 2
- 否则，dp[i][j] = dp[i + 1][j - 1] + 2
当s[i] != s[j]时，s[i, j]的最长回文子序列长度是i到j-1的最长回文子序列长度和i+1到j的最长回文子序列长度的最大值。

遍历顺序：从下往上，从左往右

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