[动态规划]代码随想录总结（自用）

  • 开发
  • 32

文章目录

动态规划入门

斐波那契数

力扣相关题目：
509.斐波那契数
70.爬楼梯
746.使用最小花费爬楼梯

Java代码：

class Solution {
	// 509.斐波那契数
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    // 70.爬楼梯
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[1] = 1; 
        dp[2] = 2;
        for (int i = 3; i <= n; i ++)
        {
             dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    // 746.使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i ++)
        {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[n];
    }
}

路径问题

力扣相关题目：
62.不同路径
63.不同路径2

Java代码：

class Solution {
	// 62.不同路径
    public int uniquePaths(int m, int n) {
        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
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i ++) dp[i][0] = 1;
        for (int i = 0; i < n && obstacleGrid[0][i] == 0; i ++) dp[0][i] = 1;

        for (int i = 1; i < m; i ++)
        {
            for (int j = 1; j < n; j ++)
            {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
    
}

整数拆分

力扣相关题目：
343.整数拆分

Java代码：

class Solution {
	// 343.整数拆分
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        // 初始条件：2可以拆成1*1=1
        dp[2] = 1;
        for (int i = 3; i <= n; i ++)
        {
            for (int j = 1; j <= i/2; j ++)
            {
            	// 可以拆成两个数i-j和j；也可以拆成j和dp[i-j]
                dp[i] = Math.max(dp[i], Math.max((i-j)*j,j*dp[i - j]));
            }
        }
        return dp[n];
    }
    
}

动态规划在树中的应用

力扣相关题目：
96.不同的二叉搜索树
Java代码：

class Solution {
	// 96.不同的二叉搜索树
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <=n; i ++)
        {
            for (int j = 1; j <= i; j ++)
            {
            	// 以dp[3]为例：
            	// dp[3]=元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 
            	// + 元素3为头结点搜索树的数量
            	// 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
            	// 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
            	// 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
            	// 所以 dp[3]=dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
                dp[i] += dp[j - 1]*dp[i - j];
            }
        }
        return dp[n];
    }
    
}

背包问题

本篇主要记录01背包和完全背包问题

01背包

你有一个背包，最多能容纳的体积是V，现在有n个物品，第i个物品的体积为 v i v_i vi​ ,价值为 w i w_i wi​,则
(1) 求这个背包至多能装多大价值的物品？
(2) 若背包恰好装满，求至多能装多大价值的物品？

牛客网：
【模板】01背包

Java代码：

import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int V = in.nextInt();
             
            int[] weight = new int[n];
            int[] value = new int[n];
            int[] dp = new int[V+1];
 
            for (int i = 0; i < n; i ++)
            {
                weight[i] = in.nextInt();
                value[i] = in.nextInt();
            }
 			// 外循环遍历物品
            for (int i = 0; i < n; i ++)
            {
            	// 内循环倒着遍历容量
                for (int j = V; j >= weight[i]; j --)
                {
                	// 装该物品：dp[j - weight[i]] + value[i]
                	// 不装该物品：dp[j]
                	// 求最大值
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
            System.out.println(dp[V]);
 
            int[] dp1 = new int[V+1];
            Arrays.fill(dp1,Integer.MIN_VALUE);
            dp1[0] = 0;
 
            for (int i = 0; i < n; i ++)
            {
                for (int j = V; j >= weight[i]; j --)
                {
                    dp1[j] = Math.max(dp1[j], dp1[j - weight[i]] + value[i]);
                }
            }
            if (dp1[V] < 0) dp1[V] = 0;
            System.out.println(dp1[V]);
 
        }
    }
}

力扣相关题目：
416.分割等和子集
1049.最后一块石头的重量II
494.目标和
474.一和零

Java代码：

class Solution {
	// 416.分割等和子集
	// 数组中找到子集，该子集总和为sum/2
	// 背包容量为sum/2,物品为数组nums，物品重量为nums[i]，价值也为nums[i]
	// dp[target] == target?
    public boolean canPartition(int[] nums) {

        int n = nums.length;
        if (n < 2) return false;
        int sum = 0;
        for(int i = 0; i < n; i ++)
        {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;
		// 所以该题等价于背包的容量V=target=sum/2
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i ++)
        {
            for (int j = target; j >= nums[i]; j --)
            {
                dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target) return true;
        return false;
    }
    // 1049.最后一块石头的重量II
    // 这道题同样是背包容量为sum/2，与416.分割等和子集思路一致
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int i = 0; i < n; i ++)
        {
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; 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]) - dp[target];
    }
    // 494.目标和
    // 容量为(sum + target) / 2的背包问题
    // 与前两个题不一样的是，求方案个数
    // 递归条件一般是dp[j] += dp[j - nums[i]]
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i ++)
        {
            sum += nums[i];
        }
        if ((sum + target) % 2 != 0) return 0;
        if (Math.abs(target) > sum) return 0;
        int t = (sum + target) / 2;
        if (t < 0) t = -t;
        int[] dp = new int[t + 1];
        dp[0] = 1;

        for (int i = 0; i < n; i ++)
        {
            for (int j = t; j >= nums[i]; j --)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[t];
    }
    // 494.一和零
    // 之前的题目背包容量是一维的，即target
    // 该题目背包容量为二维的，即m与n，需要二维数组dp
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        // 遍历物品（strs数组）
        for(String str:strs)
        {
        	// oneNum和zeroNum为物品的重量
            oneNum = 0;
            zeroNum = 0;
            for (int i = 0; i < str.length(); i ++)
            {
                if (str.charAt(i) == '0') zeroNum ++;
                else oneNum ++;
            }
			// 遍历背包容量
            for(int i = m; i >= zeroNum; i --)
            {
                for (int j = n; j >= oneNum; j --)
                {
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum][j-oneNum] + 1);
                }
            }
        }
        return dp[m][n];

    }
    
}

完全背包

你有一个背包，最多能容纳的体积是V，现在有n个物品，每种物品有任意多个，第i个物品的体积为 v i v_i vi​ ,价值为 w i w_i wi​,则
(1) 求这个背包至多能装多大价值的物品？
(2) 若背包恰好装满，求至多能装多大价值的物品？

牛客网：
【模板】完全背包

代码和01背包的区别为在于遍历背包容量：
1.01背包倒序遍历

for (int j = V; j >= weight[i]; j --)
{
    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}

2.完全背包顺序遍历

for (int j = weight[i]; j <= V; j ++)
{
    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}

Java代码：

import java.util.Scanner; 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int V = in.nextInt();
             
            int[] weight = new int[n];
            int[] value = new int[n];
            int[] dp = new int[V+1];
 
            for (int i = 0; i < n; i ++)
            {
                weight[i] = in.nextInt();
                value[i] = in.nextInt();
            }
 
            for (int i = 0; i < n; i ++)
            {
            	// 这个地方与01背包不同
                for (int j = weight[i]; j <= V; j ++)
                {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
            System.out.println(dp[V]);
 
            int[] dp1 = new int[V+1];
            Arrays.fill(dp1,Integer.MIN_VALUE);
            dp1[0] = 0;
 
            for (int i = 0; i < n; i ++)
            {
                for (int j = weight[i]; j <= V; j ++)
                {
                    dp1[j] = Math.max(dp1[j], dp1[j - weight[i]] + value[i]);
                    if (dp1[j] < 0)
                    {
                        dp1[j] = Integer.MIN_VALUE;
                    }
                }
            } 
            System.out.println(dp1[V] == Integer.MIN_VALUE ? 0: dp1[V]);
        }
    }
}

力扣相关题目：
518.零钱兑换II
322.零钱兑换
279.完全平方数
377. 组合总和 Ⅳ
139.单词拆分

Java代码：

class Solution {
	// 518.零钱兑换II
	// 求组合数问题：dp[j] += dp[j - coins[i]];
    public int change(int amount, int[] coins) {
        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];
    }
    // 322.零钱兑换
    // 这次不是求最大值，而是求最小值
    // 在初始化是需要Integer.MAX_VALUE填充
    public int coinChange(int[] coins, int amount) {
        int maxn = Integer.MAX_VALUE;
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,maxn);
        dp[0] = 0;
        for (int i = 0; i < n; i ++)
        {
            for (int j = coins[i]; j <= amount; j ++)
            {
                if (dp[j - coins[i]] != maxn) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == maxn ? -1:dp[amount];
    }
    // 279.完全平方数
    public int numSquares(int n) {
        int maxn = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];

        Arrays.fill(dp,maxn);
        dp[0] = 0;

        for (int i = 1; i*i <= n; i ++)
        {
            for (int j = i*i; j <= n; j ++)
            {
                if (dp[j - i*i] != maxn) dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
            }
        }
        return dp[n] == maxn ? -1 : dp[n];
    }
    // 377. 组合总和 Ⅳ
    // 求排列（有顺序的），不是组合
    // 先遍历容量
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (i >= nums[j]) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
    // 139.单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i ++)
        {
            for (String word:wordDict)
            {
                int len = word.length();
                if (i >= len && dp[i - len] && word.equals(s.substring(i - len,i))) dp[i] = true;
            }
        }
        return dp[n];

    }
    
    
}

背包总结：

打家劫舍

力扣相关题目：
198.打家劫舍
213.打家劫舍II
337.打家劫舍 III

Java代码：

class Solution {
	// 198.打家劫舍
	// 一个数组相邻之间不能连着偷，如何偷才能得到最大金钱
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for (int i = 2; i < n; i ++)
        {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
    // 213.打家劫舍II
    // 数组成环了，然后相邻的不能连着偷
    // 情况一：考虑包含首元素，不包含尾元素
    // 情况二：考虑包含尾元素，不包含首元素
    // 两种情况求最大
    public int robRange(int[] nums, int start, int end)
    {
        if (start == end) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end;  i++)
        {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
    // 337.打家劫舍 III
    // 采用后序遍历
    // 如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
    // 如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
    // 最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;

        int result1 = robRange(nums,0,n - 2);
        int result2 = robRange(nums,1,n - 1);
        return Math.max(result1,result2);
    }
    public int[] robTree(TreeNode root)
    {
        if (root == null) return new int[]{0,0};
        int[] left = robTree(root.left);
        int[] right = robTree(root.right);

        int var1 = root.val + left[0] + right[0];
        int var2 = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

        return new int[] {var2,var1};
    }
    public int rob(TreeNode root) {
        int[] result = robTree(root);
        return Math.max(result[0],result[1]);
    }
    
    
}

买卖股票的最佳时机（状态转换）

力扣相关题目：
121. 买卖股票的最佳时机
122.买卖股票的最佳时机II
123.买卖股票的最佳时机III
188.买卖股票的最佳时机IV
309.最佳买卖股票时机含冷冻期
714.买卖股票的最佳时机含手续费

Java代码：

class Solution {
	// 121. 买卖股票的最佳时机
	// dp[i][0]表示第i天持有股票所得最多现金
	// dp[i][1]表示第i天不持有股票所得最多现金
	// 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来：
	// 1.第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
	// 2.第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
	// dp[i][0] = max(dp[i - 1][0], -prices[i]);
	// 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
	// 1.第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
	// 2.第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
	// dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;

        int[][] dp = new int[n][2];

        dp[0][0] -= prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < n; 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[n - 1][1];
    }
    // 122.买卖股票的最佳时机II
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][2];
        dp[0][0] -= prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < n; 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[n - 1][1];
    }
    // 123.买卖股票的最佳时机III
    // dp有五个状态
    // 0.没有操作 （其实我们也可以不设置这个状态）
    // 1.第一次持有股票
	// 2.第一次不持有股票
	// 3.第二次持有股票
	// 4.第二次不持有股票
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][5];
        dp[0][1] -= prices[0];
        dp[0][3] -= prices[0];

        for (int i = 1; i < n; i ++)
        {
            dp[i][0] = dp[i - 1][0];
            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]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[n - 1][4];
    }
    // 188.买卖股票的最佳时机IV
    // 上一题拓展到通用的k个股票
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][2*k + 1];
        for (int i = 1; i < 2*k; i += 2)
        {
            dp[0][i] -= prices[0];
        }

        for (int i = 1; i < n; i ++)
        {
            for (int j = 0; j < 2*k - 1; j += 2 )
            {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[n - 1][2*k];
    }
    // 309.最佳买卖股票时机含冷冻期
    // 需要结合状态转换图来理解
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][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][1] - prices[i], dp[i - 1][3] - 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][1], Math.max(dp[n - 1][2], dp[n - 1][3]));
    }
    // 714.买卖股票的最佳时机含手续费
    //与122类似，就是多了手续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][2];
        dp[0][0] -= prices[0];

        for (int i = 1; i < n; 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 Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
    
}

最长子序列

力扣相关题目：
300.最长递增子序列
674. 最长连续递增序列
53. 最大子序和
718. 最长重复子数组

Java代码：

class Solution {
	// 300.最长递增子序列
	// dp[i]: 表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
	// 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值
	// if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
	// 最后求全局的最大值
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i < n; i ++)
        {
            for (int j = 0; j < i; j ++)
            {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
    // 674. 最长连续递增序列
    // dp[i]:以下标i为结尾的连续递增的子序列长度
    // 以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1
    // dp[i] = dp[i - 1] + 1 与上题的区别
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int res = 1;
        int[] dp = new int[n];
        Arrays.fill(dp,1);

        for (int i = 1; i < n; i ++)
        {
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
            if (res < dp[i]) res = dp[i];
        }
        return res;
    }
    // 53. 最大子序和
    // dp[i]两个方面
    // 1.dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
    // 2.nums[i]，即：从头开始计算当前连续子序列和
    // 取最大值
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int result = dp[0];

        for (int i = 1; i < n; i ++)
        {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i] > result) result = dp[i];
        }

        return result;
    }
    // 718. 最长重复子数组
    // dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
    // 与674很像
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i ++) 
        {
            if (nums1[i] == nums2[0]) dp[i][0] = 1;
        }
        for (int j = 0; j < m; j ++)
        {
            if (nums2[j] == nums1[0]) dp[0][j] = 1;
        }

        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            for (int j = 0; j < m; j ++)
            {
                if (nums1[i] == nums2[j] && i > 0 && j > 0)
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > res) res = dp[i][j];
            }
        }
        return res;
    }
     
}

最长公共序列

力扣相关题目：
1143.最长公共子序列
1035.不相交的线

Java代码：

class Solution {
	// 1143.最长公共子序列
	// dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
	// 两种情况：
	// 1. 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
	// 2.如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];

        for (int i = 1; i <= m; i ++)
        {
            for (int j = 1; j <= n; 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]);
                }
            }
        }
        return dp[m][n];
    }
    // 1035.不相交的线
    // 与上一题等价
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; 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[n][m];
    }
     
}

子序列有关（删除元素）

力扣相关题目：
392.判断子序列
115.不同的子序列
583. 两个字符串的删除操作
72. 编辑距离

Java代码：

class Solution {
	// 392.判断子序列
	// dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度
	// s[i - 1] == t[j - 1]：t中找到了一个字符在s中也出现了
	// s[i - 1] != t[j - 1]：相当于t要删除元素，继续匹配
    public boolean isSubsequence(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; 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[n][m] == n) return true;
        return false;
    }
    // 115.不同的子序列
    // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
    // s[i - 1] == t[j - 1]:
    // 1.一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]
    // 2.一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]
    // s[i - 1] != t[j - 1]：不用s[i - 1]来匹配（就是模拟在s中删除这个元素）
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i ++) dp[i][0] = 1;
        for (int j = 1; j <= m; j ++) dp[0][j] = 0;

        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; j ++)
            {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][m];
    }
    // 583. 两个字符串的删除操作
    // dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2
    // s[i - 1] == t[j - 1]:dp[i][j] = dp[i - 1][j - 1];
    // s[i - 1] != t[j - 1]：删除s的或t的
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i ++) dp[i][0] = i;
        for (int j = 0; j <= m; j ++) dp[0][j] = j;

        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; 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, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[n][m];
    }
    // 72. 编辑距离
    // 删除或添加可以都看作是删除
    // word1替换word1[i - 1]，使其与word2[j - 1]相同
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i ++) dp[i][0] = i;
        for (int j = 1; j <= m; j ++) dp[0][j] = j;

        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= m; 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], Math.min(dp[i - 1][j], dp[i][j - 1]))+1;
                }
            }
        }
        return dp[n][m];
    }
     
}

回文子串

力扣相关题目：
647. 回文子串
516.最长回文子序列

Java代码：

class Solution {
	// 647. 回文子串
	// 只考虑s[i] == t[j]的情况
	// 1.下标i 与 j相同，同一个字符例如a，当然是回文子串
	// 2.下标i 与 j相差为1，例如aa，也是回文子串
	// 3.下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                dp[i][j] = false;
            }
        }

        for (int i = n - 1; i >= 0; i --)
        {
            for (int j = i; j < n; j ++)
            {
                if (s.charAt(i) == s.charAt(j))
                {
                    if (j - i <= 1)
                    {
                        res ++;
                        dp[i][j] = true;
                    }else if (dp[i + 1][j - 1])
                    {
                        res ++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return res;
    }
    // 516.最长回文子序列
    // 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i ++) dp[i][i] = 1;
        for (int i = n - 1; i >= 0; i --)
        {
            for (int j = i + 1; j < n; 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][n - 1];
    }
     
}
阅读全部

相关推荐

  1. [动态规划]代码随想录总结（自用）

    2024-04-04 08:28:04       33 阅读

  2. 代码随想录day60 | 动态规划P17 | ● 647. ● 516.● 动态规划总结篇

    2024-04-04 08:28:04       30 阅读

  3. 代码随想录-动态规划专题

    2024-04-04 08:28:04       52 阅读

  7. 代码随想录day56 | 动态规划P16 | ● 583. ● 72. ● 编辑距离总结篇

    2024-04-04 08:28:04       40 阅读

  8. 代码随想录day35：动态规划part3

    2024-04-04 08:28:04       38 阅读

  9. 二刷代码随想录——动态规划day57

    2024-04-04 08:28:04       51 阅读

  10. 【代码随想录】【动态规划】day39:不同路径

    2024-04-04 08:28:04       39 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-04 08:28:04       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-04 08:28:04       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-04 08:28:04       87 阅读

  19. Python语言-面向对象

    2024-04-04 08:28:04       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-04 08:28:04       91 阅读

热门阅读

  3. 限制promise并行执行个数

    2024-04-04 08:28:04       39 阅读

  5. Making Anti-Palindromes

    2024-04-04 08:28:04       39 阅读

  7. ‘iostream‘ file not foundclang(pp_file_not_found)

    2024-04-04 08:28:04       38 阅读

  8. Datacom HCIP笔记-BGP协议 之二

    2024-04-04 08:28:04       38 阅读

  21. html根据屏幕分辨率大小字体自动变大缩小

    2024-04-04 08:28:04       35 阅读

  23. 前端内部技术分享---前端组件之表格组件的封装与使用（Vue3）

    2024-04-04 08:28:04       37 阅读