当前位置：首页 > article >正文

leetcode刷题——动态规划（2）

article 2025/1/1 8:02:02

198.打家劫舍

力扣题目链接(opens new window)

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

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

示例 1：
输入：[1,2,3,1]
输出：4

class Solution {
    public int rob(int[] nums) {
        // dp[i]表示有i个房屋能够抢劫的最大钱
        //不能抢相邻的，所以递推就选当前i和i-2的，或者i-1的
        // 递推：抢劫当前房屋nums[i-1]+dp[i-2] 不抢劫就是dp[i-1] 从2个选择取最大的
        // 初始化：dp[0]=0 根据递推公式是选择最大值，所以其他下标的数据为0不会影响比较
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length];

    }
}

213.打家劫舍II

力扣题目链接(opens new window)

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

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

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

class Solution {
    public int rob(int[] nums) {

        // dp[i]表示有i个房屋能够抢劫的最大钱
        // 不能抢相邻的，所以递推就选当前i和i-2的，或者i-1的
        // 递推：抢劫当前房屋nums[i-1]+dp[i-2] 不抢劫就是dp[i-1] 从2个选择取最大的
        // 初始化：dp[0]=0 根据递推公式是选择最大值，所以其他下标的数据为0不会影响比较
        // 这道题目分2种情况：考虑不包含尾部 和考虑不包含头部
        if (nums.length == 1)
            return nums[0];
        int res1 = getmax(0, nums);
        int res2 = getmax(1, nums);
        return Math.max(res1, res2);
    }

    public int getmax(int start, int[] nums) {
        // 比如nums有5个元素，那传入方法就4个元素 我们dp包括0 就需要new 5个值，所以直接就是nums.length
        int[] dp = new int[nums.length];
        dp[0] = 0;
        // 这里需要改变从数组的start开始
        dp[1] = nums[start];
        for (int i = 2; i < nums.length; i++) {
            // 这里的nums[i-1]需要改成从start开始的
            // start =0表示考虑头部数组遍历从0索引开始 =1表示考虑尾部数组遍历从1索引开始
            dp[i] = Math.max(nums[start + i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length - 1];

    }
}

337.打家劫舍 III

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

class Solution {
    public int rob(TreeNode root) {
        int[] res = Maxrob(root);
        return Math.max(res[0], res[1]);
    }

    // 后序遍历，因为需要递归函数的返回值来做下一步计算
    public int[] Maxrob(TreeNode node) {
        // 定义返回的一维数组永远包含2个元素
        // nums[0]表示不偷当前根节点的最大金额，nums[1]表示偷当前根节点获取的最大金额
        if (node == null)
            return new int[] { 0, 0 };
        // 通过递归左节点，得到左节点偷与不偷的金钱。
        int[] left = Maxrob(node.left);
        // 通过递归右节点，得到右节点偷与不偷的金钱。
        int[] right = Maxrob(node.right);
        // 情况1：抢劫当前节点，那左右孩子必须不能偷
        int val = node.val + left[0] + right[0];
        // 情况2，不抢劫当前节点，那对左右孩子偷不偷都无所谓，选择最大的返回
        int val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[] { val2, val };
    }
}

121. 买卖股票的最佳时机

力扣题目链接(opens new window)

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

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

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

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

class Solution {
    public int maxProfit(int[] prices) {
        // 贪心：遍历过程中始终保持最小值，然后每次遍历都计算当前价格-最小值，保留最大的利润
        int res=0;
        int min=prices[0];
        for(int i=1;i<prices.length;i++){
            min=Math.min(min,prices[i]);
            res=Math.max(res,prices[i]-min);
        }
        return res;
    }
}

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

力扣题目链接(opens new window)

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

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

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

示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

这道题是hard级别，直接看卡尔题解了

class Solution {
    public int maxProfit(int[] prices) {
        // 确定dp数组以及下标的含义 dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
        // 一天一共就有4个状态，
        // 第一次持有股票 dp[i][1]
        // 第一次不持有股票 dp[i][2]
        // 第二次持有股票 dp[i][3]
        // 第二次不持有股票dp[i][4]
        // 达到dp[i][1]状态，有两个具体操作：
        // 操作一：第i天买入股票了，那么dp[i][1] = - prices[i]
        // 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
        // dp[i][2]也有两个操作：
        // 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
        // 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
        // dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        // dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        // 初始化：dp[1][1] 表示第一天持有股票 dp[1][1]=-prices[0]; 去买股票了
        // dp[1][1]第一天卖出股票 那就当天买当天卖出 dp[1][2]=0;
        // 同理 dp[1][3]第二次持有股票就是dp[1][3]=-prices[0] dp[1][4]=0;
        int[][] dp = new int[prices.length + 1][5];
        dp[1][1] = -prices[0];
        dp[1][3] = -prices[0];
        for (int i = 2; i <= prices.length; i++) {
            // 表示沿用前一天第一次买入的状态或者就在第i天第一次买入，金额减少
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
            // 表示沿用前一天第一次卖出的状态或者就在第i天第一次卖出，金额增加，注意第一次卖出是基于前天第一次持有的状态
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i - 1]);
            // 表示沿用前一天第二次买入的状态或者就在第i天第二次买入，金额减少，注意第二次买入是基于前天第一次卖出的状态
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i - 1]);
            // 表示沿用前一天第二次卖出的状态或者就在第i天第二次卖出，金额增加，注意第二次卖出是基于前天第二次持有的状态
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i - 1]);
        }
        return dp[prices.length][4];
    }
}

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

力扣题目链接(opens new window)

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

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

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

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

class Solution {
    public int maxProfit(int k, int[] prices) {
        // 这个题目就是上一个的改进一下，上一个题目k=2 就需要4个变量保存状态 k个就2*k个买入卖出的状态
        // 这次我们就是抓住规律更新dp[数组】,每次买入卖出的更新规则是统一的
        int[][] dp = new int[prices.length + 1][1 + 2 * k];
        // dp[1][1] = -prices[0];
        // dp[1][3] = -prices[0];
        for (int i = 1; i <= k; i++) {
            dp[1][i * 2 - 1] = -prices[0];
        }
        for (int i = 2; i <= prices.length; i++) {
            // // 表示沿用前一天第一次买入的状态或者就在第i天第一次买入，金额减少
            // dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
            // // 表示沿用前一天第一次卖出的状态或者就在第i天第一次卖出，金额增加，注意第一次卖出是基于前天第一次持有的状态
            // dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i - 1]);
            // // 表示沿用前一天第二次买入的状态或者就在第i天第二次买入，金额减少，注意第二次买入是基于前天第一次卖出的状态
            // dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i - 1]);
            // // 表示沿用前一天第二次卖出的状态或者就在第i天第二次卖出，金额增加，注意第二次卖出是基于前天第二次持有的状态
            // dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i - 1]);
            for (int j = 1; j <= k; j++) {
                // 表示沿用前一天第k次买入的状态或者就在第i天第k次买入，金额减少，注意第k次买入是基于前天第k-1次卖出的状态
                dp[i][j * 2 - 1] = Math.max(dp[i - 1][j * 2 - 1], dp[i - 1][j * 2 - 2] - prices[i - 1]);
                // 表示沿用前一天第k次卖出的状态或者就在第i天第k次卖出，金额增加，注意第k次卖出是基于前天第k次持有的状态
                dp[i][j * 2] = Math.max(dp[i - 1][j * 2], dp[i - 1][j * 2 - 1] + prices[i - 1]);
            }
        }
        return dp[prices.length][2 * k];
    }
}

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

力扣题目链接(opens new window)

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

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

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][0]第i天持有
        // dp[i][1]第i天处于冷冻期(不持有)=第i-1天卖出去
        // dp[i][2]第i天不持有也不处于冷冻期
        // dp[i][3]第i天卖出去了(不持有)
        int[][] dp = new int[prices.length + 1][4];
        dp[1][0] = -prices[0];
        for (int i = 2; i <= prices.length; i++) {
            // 表示沿用前一天持有或前一天是冷冻期今天买入或前一天是不持有也不处于冷冻期，可以买入
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2], dp[i - 1][1]) - prices[i - 1]);
            // 处于冷冻期说明第i-1天卖出股票也就是dp[i-1][3]
            dp[i][1] = dp[i - 1][3];
            // 不持有也不冷冻就是（第i-1天不持有也不处于冷冻期或者第i-1天处于冷冻期
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
            // 今天卖出，那就是昨天或者今天持有的股票 今天卖出去
            dp[i][3] = dp[i-1][0] + prices[i - 1];
        }

        int val = Math.max(dp[prices.length][2], dp[prices.length][1]);
        return Math.max(dp[prices.length][3], val);
    }
}

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

力扣题目链接(opens new window)

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

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

返回获得利润的最大值。

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

这个题目比前面几个容易多了，状态就2个

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // dp[i][0] 表示第i天持有股票所省最多现金。  
        // dp[i][1] 表示第i天不持有股票所得最多现金 
        int[][] dp=new int[prices.length+1][2];
        dp[1][0]=-prices[0];
        dp[1][1]=0;
        for(int i=2;i<=prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i-1]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i-1]-fee);
        }
        return dp[prices.length][1];
        
    }
}

300.最长递增子序列

力扣题目链接(opens new window)

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

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

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 定义dp[i]为从0-i的所有序列中以nums[i]结尾的最大递增子序列长度，
        // 注意这个最大递增子序列一定包含nums[i]
        // 比如 【0 1 0】数组，dp[2]是以 nums[2] 也就是0结尾的最大递增子序列长度 dp[2]=1,也就是只有0
        // 这里我们控制必须以nums[i]结尾的递增序列，是为了后面比较nums[i]和nums[j]
        // 思路就是遍历完数组，得到所有dp[i]里面的一个最大值
        // 递推公式：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
        // if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
        // 举例推导 0 1 0 5 1 对应的dp数组为（1，2，1，3，2）取dp的最大值3返回
        int[] dp = new int[nums.length];
        int res = 1;
        for (int i = 0; i < nums.length; i++)
            dp[i] = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 这里的dp[j]一定是以nums[j]结尾
                // 如果当前元素大于那个尾部元素，那肯定递增序列长度加1
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

674. 最长连续递增序列

力扣题目链接(opens new window)

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

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

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

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

        // 动态规划
        int[] dp = new int[nums.length];
        int res = 1;
        for (int i = 0; i < nums.length; i++)
            dp[i] = 1;
        for (int i = 1; i < nums.length; i++) {
            // for (int j = 0; j < i; j++) {
                // 这里的dp[j]一定是以nums[j]结尾
                // 如果当前元素大于那个尾部元素，那肯定递增序列长度加1
                if (nums[i] > nums[i-1])
                    dp[i] = Math.max(dp[i], 1 + dp[i-1]);
            // }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

718. 最长重复子数组

力扣题目链接(opens new window)

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

示例：

输入：

A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
        // 这里的重复数组一定是以nums[i-1]结尾
        // 思想：就是不断遍历2个数组
        // 遍历计算A数组的每个元素作为尾部元素i时
        // B的每个元素作为重复数组的尾部元素j时，构成重复数组的最大长度
        
        int[][] dp=new int[nums1.length+1][nums2.length+1];
        int res=0;
        for(int i=1;i<=nums1.length;i++){
            for(int j=1;j<=nums2.length;j++){
                if(nums1[i-1]==nums2[j-1])
                // 一旦相等，那就考虑A和B数组各自前一个元素构成重复数组的最大长度dp[i-1][j-1]的基础上+1
                    dp[i][j]=1+dp[i-1][j-1];
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
        
    }
}

1143.最长公共子序列

力扣题目链接(opens new window)

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

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

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        // 这里的子序列可以不连续
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        int res = 0;
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else {
                    // 这道题和最长重复数组的区别在这里
                    // 数组要求必须连续，如果元素不相等，那dp[i][j]=0
                    // 而这个题目可以是不连续的序列，所以元素不相等后，就考虑减少一个text1或text2的元素
                    // 也就是dp[i][j]上方和左方的元素
                    // 每个dp[i][j]都是从左上，左，上 3个位置的元素推导来的
                    // 可能会有疑惑会不会缩减数组的2个元素，其实上方dp[i-1][j]和左方dp[i][j-1]
                    // 已经涵盖了缩减多个元素的情况了，因为他们的求解也是根据这些元素推到得出的
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

                res = Math.max(res, dp[i][j]);

            }

        }
        return res;
    }
}

1035.不相交的线

力扣题目链接(opens new window)

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

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

这个题目和最长公共子序列是一样的题目

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1]== nums2[j - 1])
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

                res = Math.max(res, dp[i][j]);

            }

        }
        return res;
    }
}

115.不同的子序列

力扣题目链接(opens new window)

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

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

Hard级别

class Solution {
    public int numDistinct(String s, String t) {
        // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
        // 初始化 dp[i][0] dp[0][j]
        // 第一行应该都是0
        // 第一列应该都是1 因为t的长度为0，那s数组可以出现一个空
        int dp[][] = new int[s.length() + 1][t.length() + 1];
        for (int j = 0; j < s.length(); j++) {
            dp[j][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))
                    // 我的误区 以为相等就是只有1种结果，应该是dp[i-1][j-1]种
                    // dp[i][j]=1+dp[i-1][j];
                    // 相等有2种情况相加：
                    // （1）考虑只回退数组s一个元素，即t的尾部元素还有可能出现在s[i-1]的前面
                    // （2）同时回退s和t数组，尾部元素就是s[i-1]
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    // 如果不相等，那就只回退数组s一个元素，看看有没有相等的，
                    // 注意不能回退t,因为你就是要保持t完整的相等的，求s的子序列等于t
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.length()][t.length()];
    }
}

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

力扣题目链接(opens new window)

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

这个和最长公共子序列一样，求出后，就可以知道该删除多少字母了

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] = 1 + dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

                }
            }
        }
        int sharelen = dp[word1.length()][word2.length()];
        return word1.length() - sharelen + word2.length() - sharelen;
    }
}

72. 编辑距离

力扣题目链接(opens new window)

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

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

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

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++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word2.length(); i++) {
            dp[0][i] = 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 {
                    // 当2个字符不相同时，有增删改 3个操作，都是操作word1
                    // （1）word1删除一个元素dp[i-1][j]+1
                    // （2）word1增加一个相同的元素 那就2个元素相等后，又回到各自前一个下标
                    // 所以其实就是 word2删除一个元素dp[i][j-1]+1
                    // 比如abc abd c和d不相等 增加元素 abcd 和 abd 比较
                    // 实际就是比较 abc 和ab 所以就是word2删除一个元素
                    // （3）word1替换成和word2一样的数据dp[i-1][j-1]+1
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;

                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

647. 回文子串

力扣题目链接(opens new window)

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

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

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

class Solution {
    public int countSubstrings(String s) {
        // dp[i][j]：表示区间范围[i,j] 的子串（包含下标i和j）是否是回文子串，如果是dp[i][j]为true，否则为false
        // 思路：在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，
        // 那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串
        // 也就是 i i+1 ... j-1 j 这个序列，比较i和j的字符，相等了再判断中间的是否相等
        // 初始化都是false
        // 遍历顺序：因为 dp[i][j]=dp[i+1][j-1]; 所有从下到上，左到右去遍历 保证j是大于等于i
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--)
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        res++;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        return res;

    }
}

516.最长回文子序列

力扣题目链接(opens new window)

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示：

1 <= s.length <= 1000
s 只包含小写英文字母

class Solution {
    public int longestPalindromeSubseq(String s) {
        // i i+1 ... j-1 j
        // dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度。
        // 递推公式：相等的时候，就看看中间序列长度dp[i+1][j-1]的最长回文
        // 不相等，就看看加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
        int[][] dp = new int[s.length()][s.length()];
        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--)
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 这里控制一下，如果i和j相邻或者i==j
                    if (j - i <= 1) {
                        dp[i][j] = j - i + 1;
                    } else
                        dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        // 注意这里的返回就是[0,len-1]之间的字符串
        return dp[0][s.length() - 1];
    }
}

动态规划完结！！！

查看全文

http://www.kler.cn/a/456500.html