代码随想录之动态规划（力扣题号）网站首页 技术交流

代码随想录之动态规划（力扣题号）

Sophia2333333331 2023-05-25 04:00:03

简介代码随想录之动态规划（力扣题号）

62 不同路径

在这里插入图片描述
很简单的dp

class Solution {
    public int uniquePaths(int m, int n) {
        //58-02
        int[][] dp = new int[m][n];
        //初始化
        for(int i = 0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i<n;i++){
            dp[0][i] = 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];

    }
}

63 不同路径2

在这里插入图片描述

和前一题的区别在于只要判断当前有障碍物就dp对应数值设为0，否则就是正常算法，还有就是初始化的时候要判断前面出现过障碍物就得设为0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //05-13
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        int f = 0;
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1){
                f = 1;
                dp[i][0] = 0;
            } 
            if(f==1) dp[i][0] = 0;//自从出现过之后就是0
            else dp[i][0] = 1;
        }
        f = 0;
        for(int j=0;j<n;j++){
            if(obstacleGrid[0][j]==1){
                f = 1;
                dp[0][j] = 0;
            } 
            if(f==1) dp[0][j] = 0;
            else dp[0][j] = 1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==0){
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
                else dp[i][j] = 0;
            }
        }
        return dp[m-1][n-1];

    }
}

343 整数拆分

在这里插入图片描述
dp[i]表示拆分整数i能取得的最大乘积
递推表达：选择dp[i-j]*j和(i-j)*j中最大的一个，两个分别表示拆成大于两个和拆成两个

看题解之后觉得容易，但是如果没放在dp章节里也不太好想

class Solution {
    public int integerBreak(int n) {
        //06
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i] = Math.max(dp[i],Math.max(dp[i-j]*j,(i-j)*j));
            }
        }
        return dp[n];

    }
}

96 不同的二叉搜索树

在这里插入图片描述
画图画了很久还是没找到规律，还是因为没有从搜索树的特点出发：总共有i个节点，每次以j为头节点，那左子树的节点有j-1个，右子树的节点的有i-j个，相乘再累加即可！！！

class Solution {
    public int numTrees(int n) {
        //14-10
        int[] dp = new int[n+1];
        if(n==1) return 1;
        Arrays.fill(dp,0);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;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];

    }
}

背包问题

二维数组

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

一维数组写法（滚动数组）倒序遍历

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

要注意先遍历物品，再遍历背包容量，然后内层要从大到小！！

int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量 不能改变
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 分割等和子集

在这里插入图片描述

第一反应是用双指针，先排序之后从两边往中间指，但是后来发现这是不行的，因为两个集合完全是可以数值交叉的，所以还是需要转成01背包问题（回溯会超时）

class Solution {
    public boolean canPartition(int[] nums) {
        //41 不能用双指针因为两个集合可以交叉 像1122是可以的 但是双指针就不行-13
        int sum = 0;
        for(int num:nums) sum+=num;
        if(sum%2==1) return false;
        int target = sum/2;
        int[] dp = new int[target+1];
        Arrays.fill(dp,0);
        for(int i=0;i<nums.length;i++){
            for(int j = target;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;

    }
}

1049 最后一块石头的重量 II

在这里插入图片描述
也不好想！！要多思考
可以转换成上一题，就是尽量分成两堆相同的，差值就是剩下的

class Solution {
    public int lastStoneWeightII(int[] stones) {
        //16
        //分成尽量相同的两堆 之后的差值就是最小的
        int sum = 0;
        for(int num:stones) sum+=num;
        int target = sum/2;
        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-dp[target]*2;

    }
}

最后dp[target]就是分成的一堆的数量之和，另一堆的重量就是sum-dp[target], 两堆之差就是sum-dp[target]*2;

494 目标和

在这里插入图片描述

用之前的回溯还是有问题，因为不用把具体的列出来，只要计算数字就可以用dp.转换为01背包问题。dp[j]表示装进j容量的包有最多多少种解法

组合类的公式

dp[j] += dp[j - nums[i]]

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
       int sum = 0;
       for(int i=0;i<nums.length;i++){
           sum+=nums[i];
       }
       if(sum+target<0||sum<target) return 0;//target可能为负 不能过大或过小
       if((sum+target)%2==1) return 0;
       int left = (sum+target)/2;
       int[] dp = new int[left+1];
       dp[0]=1;
       for(int i=0;i<nums.length;i++){
           for(int j = left;j>=nums[i];j--){
               dp[j]+=dp[j-nums[i]];
           }
       }
       return dp[left];

    }
     
}

474 0和1

在这里插入图片描述
可以转换为01背包问题，就是重量有m和n两个维度，dp[i][j]表示最多由i个0和j个1组成的最大长度

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //53
        int[][] dp = new int[m+1][n+1];//表最多装m个0 n个1
        dp[0][0]=0;
        for(String str:strs){//外层 遍历物品
            int zero = 0;
            int one = 0;
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)=='0') zero++;
                if(str.charAt(i)=='1') one++;
            }
            for(int i=m;i>=zero;i--){//内层 从大到小遍历两个维度的“背包重量”
                for(int j=n;j>=one;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zero][j-one]+1);
                }
            }
        }
        return dp[m][n];

    }
}

518 零钱兑换2

在这里插入图片描述

class Solution {
    public int change(int amount, int[] coins) {
        //12
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];

    }
}

377. 组合总和 Ⅳ

在这里插入图片描述
完全背包问题的排列数，外层遍历背包，内层遍历物品，都是从小到大遍历

class Solution {
    public int combinationSum4(int[] nums, int target) {
        //17-23
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int i=0;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if(i>=nums[j]) dp[i] +=dp[i-nums[j]];
            }
        }
        return dp[target];

    }
}

爬楼梯问题的进阶版

每次一步可以选择一个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
转换一下就是完全背包问题的排列问题！因为顺序是有关系的

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        int[] weight = {1,2,...m};
        dp[0] = 1;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < weight.length; j++) {
                if (i >= weight[j]) dp[i] += dp[i - weight[j]];
            }
        }

		//或者直接
		for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }

        return dp[n];
    }
}

322 零钱兑换

在这里插入图片描述
完全背包问题注意要把0下标和非0下标的初始化分开

class Solution {
    public int coinChange(int[] coins, int amount) {
        //31
        //完全背包问题 个数
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);//初始化一个最大的
        dp[0] = 0;//0下标
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];

    }
}

279 完全平方数

在这里插入图片描述

class Solution {
    public int numSquares(int n) {
        //完全背包  49-51
        int[] dp = new int[n+1];
        Arrays.fill(dp,n+1);//初始化最大的
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                dp[j] = Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

139 单词拆分

在这里插入图片描述

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //55 完全背包 跟顺序有关
        int n = s.length();
        boolean[] dp = new boolean[n+1];//dp[i]表示0-i下标的s可以被组成的个数
        dp[0]=true;
        for(int i=1;i<=s.length();i++){//排列问题 背包在外层
            for(String str:wordDict){//物品内层
                int len = str.length();
                if(i>=len&&dp[i-len]&&s.substring(i-len,i).equals(str)){//递推公式
                    dp[i] = true;
                }
            }
        }
        return dp[n];

    }
}

198 打家劫舍

在这里插入图片描述

class Solution {
    public int rob(int[] nums) {
        //7-12
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if(nums.length==1) return 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 打家劫舍2

在这里插入图片描述

class Solution {
    public int rob(int[] nums) {
        //14-20
        int[] dp = new int[nums.length];
        int[] dp2 = new int[nums.length];
        //偷第一家
        dp[0] = nums[0];
        if(nums.length==1) return nums[0];
        dp[1] = nums[0];//第二家就不偷了
        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        //最后一家不偷 就是dp[nums.length-2]

        //不偷第一家
        dp2[0] = 0;
        dp2[1] = nums[1];
        for(int i=2;i<nums.length;i++){
            dp2[i] = Math.max(dp2[i-2]+nums[i],dp2[i-1]);
        }
        //选两种中大的
        return Math.max(dp[nums.length-2],dp2[nums.length-1]);
    }
}

337 打家劫舍3

在这里插入图片描述
树形dp!!!其实和数组一样，就是要确定遍历方式，这里需要用后序遍历，从下往上

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = af(root);
        return Math.max(res[0],res[1]);

    }
    public int[] af(TreeNode root){
        int[] res = new int[2];
        if(root==null) return new int[]{0,0};
        int[] left = af(root.left);
        int[] right = af(root.right);//下标0：偷，下标1：不偷   0是选了当前节点值 1是没选
        res[0] = root.val+left[1]+right[1];
        res[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return res;
    }
}

121 买卖股票的最佳时机

在这里插入图片描述

class Solution {
    public int maxProfit(int[] prices) {
        //41-44
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min) min = prices[i];
            max = Math.max(max,prices[i]-min);
        }
        return max;
    }
}

122 买卖股票的最佳时机2

在这里插入图片描述

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

    }
}

123 买卖股票的最佳时机2

在这里插入图片描述

class Solution {
    public int maxProfit(int[] prices) {
        //50
        //下标为1 表示买了一次  2：表示买了一次又卖了一次 3：表示买了两次卖了一次 4：买了两次卖了两次
        
        int[][] dp = new int[prices.length][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i][0] = 0;
            dp[i][1] = Math.max(dp[i-1][1],dp[i][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i][1]+prices[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i][2]-prices[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i][3]+prices[i]);
        }
        return dp[prices.length-1][4];

    }
}

188

在这里插入图片描述
就是上一题的进阶版，把k也用数组表示即可

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

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

    }
}

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

在这里插入图片描述

状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
不持有股票状态，这里就有两种卖出股票状态
状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
状态三：今天卖出股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

确定递推公式
达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：今天买入了，有两种情况
前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

最后结果是取状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

class Solution {
    public int maxProfit(int[] prices) {
        //15
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[prices.length][4];
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));


    }
}

714 买卖股票含手续费

在这里插入图片描述

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        // 0 : 持股（买入）
        // 1 : 不持股（售出）
        // dp 定义第i天持股/不持股 所得最多现金
        dp[0][0] = -prices[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];

    }
}

740 删除并获得点数

和打家劫舍有点像，不过要求的是相邻的数字而不是相邻的nums
在这里插入图片描述

class Solution {
    public int deleteAndEarn(int[] nums) {
        //47 像打家劫舍
        if(nums.length==1) return nums[0];
        int[] count = new int[10001];
        Arrays.fill(count,0);
        for(int i=0;i<nums.length;i++){
            count[nums[i]]++;
        }
        int[] dp = new int[10001];
        dp[0] = 0;
        dp[1] = count[1];
        for(int i=2;i<dp.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+count[i]*i);
        }
        return dp[10000];
    }
}

300. 最长递增子序列

好像过了十几天没刷题，有点生疏，明明指导写法还是改了十几分钟
在这里插入图片描述

class Solution {
    public int lengthOfLIS(int[] nums) {
        //02-19
        //前面最长的
        int[] dp = new int[nums.length];//以i为字符串结尾的最长长度
        if(nums.length==1) return 1;
        Arrays.fill(dp,1);
        int res = -1;
        for(int i=1;i<nums.length;i++){
            //找前面的更小的，且dp最大的
            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;
    }
}

718 最长重复子数组

在这里插入图片描述

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //20-40
        int result = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];      
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {//注意如果没有相等就不用管，还是0，因为子数组要求是连续的
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }       
        return result;
    }
}

1143 最长公共子序列

在这里插入图片描述

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //42-47
        int res = 0;
        int[][] dp = new int[text1.length()+1][text2.length()+1];//默认初始化为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] = dp[i-1][j-1]+1;
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);//不要求连续就需要写这个
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;//其实最大值一定在最后，所以返回 dp[text1.length()][text2.length()] 也一样

    }
}

1035 不相交的线

在这里插入图片描述
其实就是找最长公共子序列的个数即可

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        //01-03
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        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] = dp[i-1][j-1]+1;
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[nums1.length][nums2.length];

    }
}

53 最大子数组和

在这里插入图片描述
连续子数组

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

    }
}

392 判断子序列

在这里插入图片描述

class Solution {
    public boolean isSubsequence(String s, String t) {
        //42-46
        int[][] dp = new int[s.length()+1][t.length()+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-1]+1;
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        if(dp[s.length()][t.length()]==s.length()) return true;
        else return false;

    }
}

115 不同的子序列

在这里插入图片描述

第一眼没有想出来，还是看了题解，主要是递推公式的变化。因为要求s中包含t，所以递推的时候考虑删掉s中的字符

class Solution {
    public int numDistinct(String s, String t) {
        //47
        int[][] dp = new int[s.length()+1][t.length()+1];
        for(int i=0;i<s.length();i++){
            dp[i][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-1]+dp[i-1][j];
                //dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[s.length()][t.length()];

    }
}

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

在这里插入图片描述

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

这里dp数组的定义有点点绕，大家要撸清思路。

确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候
当word1[i - 1] 与 word2[j - 1]不相同的时候
当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

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

class Solution {
    public int minDistance(String word1, String word2) {
        //01
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        //初始化
        for(int i=0;i<=word1.length();i++){//记得要初始化到len+1位
            dp[i][0] = i;
        }
        for(int i=0;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 dp[i][j] = Math.min(dp[i-1][j-1]+2,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

72 编辑距离

在这里插入图片描述

class Solution {
    public int minDistance(String word1, String word2) {
        //57-05
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0] = i;
        }
        for(int i=0;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{
                    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 回文子串个数

在这里插入图片描述

class Solution {
    int res = 0;
    public int countSubstrings(String s) {
        //20 从中心向两边扩展        
        for(int i=0;i<s.length();i++){
            func(s,i,i);
            func(s,i,i+1);
        }
        return res;

    }
    public void func(String s, int begin, int end){
        while(begin>=0&&end<s.length()&&begin<=end&&s.charAt(begin)==s.charAt(end)){
            begin--;
            end++;
            res++;            
        }
    }
}

最长回文子串

class Solution {
    public int longestPalindromeSubseq(String s) {
        //32
        int res = 0;
        for(int i=0;i<s.length();i++){
            res = Math.max(res,Math.max(func(s,i,i),func(s,i,i+1)));
        }
        return res;

    }
    public int func(String s, int begin, int end){

        while(begin>=0&&end<s.length()&&begin<=end&&s.charAt(begin)==s.charAt(end)){
            begin--;
            end++;

        }
        return end-begin-1;
    }
}

回文子串是要连续的，回文子序列可不是连续的！回文子串，回文子序列都是动态规划经典题目。

516 最长回文子序列

在这里插入图片描述

class Solution {
    public int longestPalindromeSubseq(String s) {
        //32
        int[][] dp = new int[s.length()][s.length()];
        for(int i=s.length()-1;i>=0;i--){//递推顺序要从下往上，从左往右
            dp[i][i]=1;//初始化
            for(int j=i+1;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;
                else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }

}

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
【数据结构】顺序表和链表（上）（附leetc...

下一篇
python算法中的排序算法（详解）...

站长推荐

U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效)

您现在的位置是：首页 >技术交流 >代码随想录之动态规划（力扣题号）网站首页技术交流

代码随想录之动态规划（力扣题号）

62 不同路径

63 不同路径2

343 整数拆分

96 不同的二叉搜索树

背包问题

416 分割等和子集

1049 最后一块石头的重量 II

494 目标和

474 0和1

518 零钱兑换2

377. 组合总和 Ⅳ

爬楼梯问题的进阶版

322 零钱兑换

279 完全平方数

139 单词拆分

198 打家劫舍

213 打家劫舍2

337 打家劫舍3

121 买卖股票的最佳时机

122 买卖股票的最佳时机2

123 买卖股票的最佳时机2

188

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

714 买卖股票含手续费

740 删除并获得点数

300. 最长递增子序列

718 最长重复子数组

1143 最长公共子序列

1035 不相交的线

53 最大子数组和

392 判断子序列

115 不同的子序列

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

72 编辑距离

647 回文子串个数

最长回文子串

516 最长回文子序列

上一篇 【数据结构】顺序表和链表（上）（附leetc...

下一篇 python算法中的排序算法（详解）...

站长推荐

上一篇
【数据结构】顺序表和链表（上）（附leetc...

下一篇
python算法中的排序算法（详解）...