开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【Leetcode 动态规划专题】 -> 正文阅读

[数据结构与算法]【Leetcode 动态规划专题】

一、一般问题系列
- 1.1、题目汇总
二、路径规划系列
- 2.1、题目汇总
三、背包系列
四、打家劫舍系列
- - - 198. 打家劫舍
    - 213. 打家劫舍 II
五、股票问题系列
六、子序列子数组问题系列
- 题目汇总
七、字符串问题系列
- 题目汇总
Reference

动态规划的核心就是最优化问题。核心是穷举。

判断可不可以用动态规划：当前的状态取决于前一个时刻的状态。

动态规划的特点：
1、重叠子问题
2、状态转移方程
3、最优子结构

解题套路：
1、明确状态
2、明确选择
3、明确dp函数/数组的定义
4、明确base case
在这里插入图片描述

一、一般问题系列

1.1、题目汇总

leetcode 509. 斐波那契数

leetcode 509. 斐波那契数.

class Solution:
    def fib(self, n: int) -> int:
        # dp[i]表示第i个斐波那契数
        if n < 2: return n
        dp = [0 for i in range(n+1)]
        dp[0], dp[1] = 0, 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

leetcode 70. 爬楼梯

leetcode 70. 爬楼梯.

class Solution:
    def climbStairs(self, n: int) -> int:
        # dp[i]表示爬到i阶有多少种方法
        if n <= 2: return n
        dp = [0 for i in range(n+1)]
        dp[1], dp[2] = 1, 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

leetcode 343. 整数拆分

343. 整数拆分.

class Solution:
    def integerBreak(self, n: int) -> int:
        # dp[i]表示整数i，将其拆分成k个数（k>=2）的最大乘积
        if n == 1: return 1
        if n == 2: return 1
        if n == 3: return 2
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        for i in range(2, n+1):
            for j in range(1, i):  # 对整数i从1开始拆分
                # 整数i拆分后的最大乘积
                # 1、直接将i拆分成两个整数相加的最大乘积 = j * (i-j)
                # 2、拆成两个以上的整数的最大乘积 = j * dp[i-j]
                dp[i] = max(dp[i], j * (i-j), j * dp[i - j]) 
        return dp[n]

剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫环问题难地推公式没懂）

剑指 Offer 62. 圆圈中最后剩下的数字.

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n == 1: return 0
        dp = [0 for i in range(n+1)]
        dp[1] = 0
        for i in range(2, n+1):
            dp[i] = (dp[i-1] + m) % i
        return dp[n]

二、路径规划系列

2.1、题目汇总

leetcode 62. 不同路径

62. 不同路径.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # dp[i][j]表示左上角到达第i行第j列位置的路径总数
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if m == 0 or n == 0 or not obstacleGrid or obstacleGrid[0][0] == 1: return 0
        dp = [[0 for _ in range(n)] for _ in range(m)]  # 初始化dp都为0
        for i in range(n):  # 初始化第一行  
            # 如果出现一个障碍 后面就不用比较了 全是0
            if obstacleGrid[0][i] == 1: break  
            dp[0][i] = 1
        for j in range(m):  # 初始化第一列
            if obstacleGrid[j][0] == 1: break
            dp[j][0] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

leetcode 63. 不同路径 II

63. 不同路径 II.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # dp[i][j]表示左上角到达第i行第j列位置的路径总数
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if m == 0 or n == 0 or not obstacleGrid or obstacleGrid[0][0] == 1: return 0
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(n):  # 初始化第一行   
            if obstacleGrid[0][i] == 1: break
            dp[0][i] = 1
        for j in range(m):  # 初始化第一列
            if obstacleGrid[j][0] == 1: break
            dp[j][0] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

leetcode 64. 最小路径和

64. 最小路径和.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # dp[i][j]表示左上角到达第i行第j列这个位置的最小路径和
        m, n = len(grid), len(grid[0])
        dp = [[grid[j][i] for i in range(n)] for j in range(m)]  
        for i in range(1, n):  # 初始化第1行
            dp[0][i] += dp[0][i-1]
        for j in range(1, m):  # 初始化第一列
            dp[j][0] += dp[j-1][0]
        for i in range(1, m):  
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j]+dp[i][j], dp[i][j-1]+dp[i][j])
        return dp[-1][-1]

三、背包系列

3.1、0-1背包问题

0-1背包问题：有N件（0~n-1）物体和一个最多能放W重量的背包，第i件物体的重量是weight[i]，价值是value[i]。每件物体只能放一次，求解哪些物体放入背包里物体价值最大？

二维dp：

确定dp数组及其含义
二维数组dp[i][j]，表示从下标为0~i的物体中任意取，放入容量为j的背包中，价值总和最大值为dp[i][j]；
状态转移方程/递推公式
dp[i][j]的状态可以由两个方向推导而来：
A、dp[i-1][j]：表示第 i 个物体我不考虑放不放，那么背包容量为 j ，取前i个物体的最大价值就等于背包容量为 j ，取前 i-1 个物体的最大价值；
B、value[i] + dp[i-1][j-weight[i]：表示第i个物体我要考虑放不放的情况下，那么只需要计算在背包容量为 j-weight[i] 的情况下，从前 i-1 个物体中取的最大价值；
所以dp[i][j] = max(dp[i-1][j]，value[i] + dp[i-1][j-weight[i]])

确定dp初始化方式（由递推公式决定）：
背包容量为0的话，什么物体都放不下，最大价值永远都是0，即dp[0~][0] = 0；
只放物品0的话，背包容量大于等于物品0的重量时等于物品0的value，小于物品0的重量时等于0；

dp = [[0 for _ in range(bagWegiht+1)] for _ in range(len(weight))]   # [物品个数行, 背包重量列]
for j in (bagWeight, weight[0]-1, -1):  # 得放的下0物品
    dp[0][j] = dp[0][j-wieght[0]] + value[0]
    # dp[0][j] = value[0]   可以这样写吗

确定遍历顺序
对于二位dp的背包问题，两层for循环是可以颠倒的

for i in range(1, len(weight)):     # 遍历物品   0~n-1  n个物品
	for j in range(1, bagWegiht+1):   # 遍历背包容量  0~m  包括容量0
		# 如果当前包的容量放不下当前物品i, 那么就不放，dp[i][j]继续保持前面的累积最大价值
		if j < weight[i]: dp[i][j] = dp[i-1][j]
		else:
			# 动态转移方程
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+values[i])

for j in range(1, bagWeight+1):   # 遍历背包容量
	for i in range(1, len(weight)):   # 遍历物品
		if j < weight[i]: dp[i][j] = dp[i-1][j]
		else:
			# 动态转移方程
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+values[i])

一维dp：

确定dp数组及其含义
一维数组dp[j]，表示容量为j的背包中，价值总和最大值为dp[j]；
状态转移方程/递推公式
dp[i][j]的状态可以由两个方向推导而来：
A、dp[j]：先考虑我不放第 i 个物体，因为二维数组中此时是：dp[i-1][j] 那么我们使用滚动数组，将i-1的情况直接覆盖在当前层，此时dp[j]就等价于二维数组中的dp[i-1][j]；
B、value[i] + dp[j-weight[i]：表示我要放第i个物体，那么只需要计算在背包容量为 j-weight[i] 的情况下，从前 i-1 个物体中取的最大价值，二维数组是value[i] + dp[i-1][j-weight[i]，使用滚动数组，把第i-1行的数子覆盖到当前层，所以值为value[i]+dp[j-weight[i]]；
所以dp[j] = max(dp[j]，value[i] + dp[j-weight[i]])
确定dp初始化方式（由递推公式决定）：
dp[0]=0 其他位置全部初始化为0
```
dp = [0 for _ in range(bagWegiht+1)]   # [背包重量]
```

确定遍历顺序
对于二位dp的背包问题，两层for循环是可以颠倒的

 for i in range(len(weight)):   # 遍历物品
	 for j in range(bagWeight, weight[i]-1, -1):   # 倒序遍历背包容量
		 dp[j] = max(dp[j], dp[j-weight[i]]+value[i])

模板：

在这里插入代码片

解题思路

传统背包问题：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，能够达到的最大重量?最多能装多少？公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
转型问题1：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，能否找到重量为j的组合？能否装满背包？公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

转型问题1是可以等价用传统背包问题等价的，只要在遍历每个物体结束的时候，比较下当前最大重量是否等于target即可：
```
 		for i in range(1, len(nums)):
 		    for j in range(1, bagweight+1):
 		        if j < nums[i]: dp[i][j] = dp[i-1][j]
 		        else:
 		            dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
 		        if dp[i][bagweight] == bagweight: return True
 		return False
```
转型问题2：dp[i][j]表示在背包容量为j的情况下，从前i个物体中任意选取若干个物体，找到重量为j的组合数目？装满背包有几种方法？公式：dp[j] += dp[j - nums[i]]

题目汇总

416. 分割等和子集

416. 分割等和子集.

视频讲解.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 一、二维数组dp
        if sum(nums) % 2 == 1: return False
        bagweight = sum(nums) // 2
        # dp[i][j]定义：在背包容量为j的情况下，从前i个数组元素中任取元素能够达到的最大重量
        dp = [[0 for _ in range(bagweight+1)] for _ in range(len(nums))]
        for j in range(bagweight, nums[0]-1, -1): 
            dp[0][j] = nums[0]
        for i in range(1, len(nums)):
            for j in range(1, bagweight+1):
                if j < nums[i]: dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
                if dp[i][bagweight] == bagweight: return True
        return False
        
        # 二、一维数组dp
        if sum(nums) % 2 == 1: return False
        bagweight = sum(nums) // 2
        # dp[j] 表示背包容量为j的情况下，给定数组能达到的最大重量
        # dp[0]=0  明显容量为0的情况下 达到的最大重量也为0
        dp = [0 for j in range(bagweight+1)]
        for i in range(len(nums)):
            for j in range(bagweight, nums[i]-1, -1):
                if j >= nums[i]:
                    dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
                if dp[bagweight] == bagweight: return True
        return False

494. 目标和

494. 目标和.

文字讲解.

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 设数组中添加'-'元素的总和为neg  则添加'+'的总和为sum_nums-neg
        # (sum_nums-neg) - neg = target => neg = (sum_nums-target)//2
        # 所以问题：通过上述方法构造的、运算结果为target的不同表达式数目 等价于
        # 求通过上述方法构造的、总和（负数）为neg的不同表达式数目
        sum_nums = sum(nums)
        if (sum_nums - target) % 2 == 1: return 0
        if target > sum_nums: return 0
        bagweight = (sum_nums - target) // 2
        # dp[j]表示当前填满j这么大的包，有dp[j]种办法
        dp = [0 for _ in range(bagweight+1)]
        # 装满容量为0的包 有1种方法 那就是装0件物品
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagweight, nums[i]-1, -1):
                dp[j] += dp[j-nums[i]]
        return dp[-1]

3.2、完全背包问题

模板：

def test_complete_pack1(nums):
    bagweight = ?  # 这里具体问题具体分析  
    # dp[j]表示背包容量为j，背包最大能装多少的重量
    dp = [0 for _ in range(bagweight + 1)]
    for i in range(len(nums)):
        for j in range(nums[i], bagweight + 1):
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
    return dp[-1]

题目汇总

518. 零钱兑换 II

518. 零钱兑换 II.

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # dp[j]表示的是装满容量为j的背包有多少种方法
        dp = [0 for _ in range(amount+1)]
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                if j >= coins[i]:
                    dp[j] += dp[j-coins[i]]
        return dp[-1]

322. 零钱兑换

322. 零钱兑换.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[j]表示装满容量为j的背包最少需要多少个硬币
        # 注意这里求至少那么初始化就要设置一个较大的数  求最大就要设置一个较小的数
        dp = [float('inf') for _ in range(amount+1)]
        dp[0] = 0  # 装满容量为0的背包至少需要0个
        for i in range(len(coins)):
            for j in range(coins[i], amount+1):
                if j >= coins[i]:
                    # 如果不选coins[i]就是dp[j]个
                    # 如果选coins[i]就是dp[j-coins[i]]+1个 注意要加1 
                    dp[j] = min(dp[j], dp[j-coins[i]]+1)
        return dp[-1] if dp[-1] != float('inf') else -1

四、打家劫舍系列

【专题讲解】打家劫舍 leetcode 198 213 337.

198. 打家劫舍

198. 打家劫舍.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]

        # dp[i]表示前i家能抢的最高金额
        dp = [0 for _ in range(len(nums))]
        dp[0] = nums[0]  # 前1家抢的最高金额=nums[0]
        dp[1] = max(nums[0], nums[1])  # 前2家抢的最高金额=max(nums[0],nums[1])
        for i in range(2, len(nums)):
            # 前i家抢的最高金额可能有两种情况：
            # 1、不抢第i家 那么前i家抢的最高金额=前i-1抢的最高金额
            # 2、抢第i家，那么前i家抢的最高金额=前i-1家抢的最高金额+第i家的金额
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[-1]

213. 打家劫舍 II

213. 打家劫舍 II.

class Solution:
    def helper(self, nums):
        if len(nums) <= 0: return 0
        if len(nums) == 1: return nums[0] 
        # dp[i]表示前i个房屋抢劫 抢的最大金额
        dp = [0 for _ in range(len(nums))]
        dp[0] = dp[0]
        dp[1] = max(dp[0], dp[1])
        for i in range(len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[-1]

    def rob(self, nums: List[int]) -> int:
        if len(nums) <= 0: return 0
        if len(nums) == 1: return nums[0]
        # 1、不抢头 不抢尾
        nums1 = self.helper(nums[1:-1])
        # 2、抢头 不抢尾
        nums2 = self.helper(nums[:-1])
        # 3、不抢头 抢尾
        nums3 = self.helper(nums[1:])
        return max(nums1, nums2, nums3)

五、股票问题系列

LeetCode121-123 动态规划解决股票问题
 LeetCode188+LeetCode309+LeetCode714 动态规划解决股票问题

121. 买卖股票的最佳时机

题意：求买卖一只股票获得的最大利润（只能完成一次交易）

121. 买卖股票的最佳时机.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 一、二维数组
        # 状态：i   0未持股/1持股
        # dp[i][0]表示第i天，未持股状态下，所获最大利润
        # dp[i][1]表示第i天，持股状态下，所获最大利润
        if len(prices) < 2: return 0
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        dp[0][0], dp[0][1] = 0, -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            # 如果是dp[i-1][0]-prices[i] 说明昨天没持股就有利润了 说明之前有过交易 不符合题意 
            # 所以这里要写-prices[i] 表面昨天没有持股且没有利润 所以当前利润为0-prices[i]
            dp[i][1] = max(dp[i-1][1], - prices[i])
        return dp[len(prices)-1][0]

        # 一维数组
        if len(prices) < 2: return 0
        # dp[0]今天未持股的状态下 所获最大利润
        # dp[1]今天持股状态下 所获最大利润
        dp = [0 for _ in range(2)]
        dp[0], dp[1] = 0, -prices[0]
        for i in range(1, len(prices)):
            dp[0] = max(dp[0], dp[1] + prices[i])
            dp[1] = max(dp[1], -prices[i])
        return dp[0]

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

题意：可以买卖多次（无限次），但是一个时刻只能持有一支股票，求最大利润？

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 1、二维数组
        # i  0未持股/1持股
        # dp[i][0] 第i天，在未持股的状态下，获得的最大利润
        # dp[i][1] 第i天，在持股的状态下，获得的最大利润
        if len(prices) == 0: return 0
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        dp[0][0], dp[0][1] = 0, -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        # 因为可以买卖多次，所以昨天没持股的情况下是可能会有利润的 
        # 所以用dp[i-1][0]-prices[i]得到昨天没持股，今天持股的最大利润
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
        return dp[len(prices)-1][0]

        # 2、一维数组
        if len(prices) == 0: return 0
        dp = [0, -prices[0]]
        for i in range(1, len(prices)):
            dp[0] = max(dp[0], dp[1] + prices[i])
            dp[1] = max(dp[1], dp[0] - prices[i])
        return dp[0]

309. 最佳买卖股票时机含冷冻期（包含I、II 代码通过了但是有疑问？？？）

题意：可以买卖无数次，且一个时刻只能持有一支股票(不能同时参与多笔交易)，卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)，求最大利润？

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0
        # dp[i][j]代表第i天持股状态为j的情况下，最大的利润
        # dp[i][0] = max(dp[i-1][0], dp[i-1][1]+price[i])
        # dp[i][1] = max(dp[i-1][1], dp[i-2][0]-price[i])
        dp = [[0 for _ in range(2)] for _ in range(len(prices))]
        # base case 第一天
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            # dp[i-1][0]-prices[i]表示昨天没有持有股票且今天我买进股票 
            # 但是是有条件的 如果昨天卖出了股票，那么我今天是无法买入股票的
            dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
        return dp[len(prices)-1][0]

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

题意：最多可以买卖2次，且一个时刻只能持有一支股票(不能同时参与多笔交易)，求最大利润？

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 1、二维dp
        # dp[i][j][k]代表第i天，持股状态为j，交易次数（买+卖为1次）为k的情况下，所获得的最大利润
        if len(prices) == 0: return 0
        dp = [[[0 for _ in range(3)] for _ in range(2)]for _ in range(len(prices))]
        dp[0][0][0] = 0
        dp[0][1][0] = -prices[0]
        dp[0][0][1] = dp[0][1][1] = dp[0][0][2] = dp[0][1][2] = float('-inf')  # 不可能事件
        
        for i in range(1, len(prices)):
            dp[i][0][0] = 0
            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])
            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])
            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])
            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])
            dp[i][1][2] = float('-inf')  # 不可能事件
        return max(0, dp[len(prices)-1][0][1], dp[len(prices)-1][0][2])

        # 2、一维dp
        if len(prices) == 0: return 0
        dp = [[0 for _ in range(3)] for _ in range(2)]
        dp[0][0] = 0
        dp[1][0] = -prices[0]
        dp[0][1] = dp[1][1] = dp[0][2] = dp[1][2] = float('-inf')  # 不可能事件
        
        for i in range(1, len(prices)):
            dp[0][0] = 0
            dp[1][0] = max(dp[1][0], dp[0][0]-prices[i])
            dp[0][1] = max(dp[0][1], dp[1][0]+prices[i])
            dp[1][1] = max(dp[1][1], dp[0][1]-prices[i])
            dp[0][2] = max(dp[0][2], dp[1][1]+prices[i])
            dp[1][2] = float('-inf')  # 不可能事件
        return max(0, dp[0][1], dp[0][2])

188. 买卖股票的最佳时机 IV（包含III）

题意：最多可以买卖k次，且一个时刻只能持有一支股票(不能同时参与多笔交易)，求最大利润？

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

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 1、二维dp
        if len(prices) == 0: return 0
        # dp[i][j][k]代表第i天，持股状态为j，交易次数为K，所获取的最大利润
        # dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k-1]+prices[i])
        # dp[i][1][k] = max(dp[i-1][1][k], dp[i-1][0][k]-prices[i])
        dp = [[[0 for _ in range(k+1)] for _ in range(2)] for _ in range(len(prices))]
        # base case 第一天
        dp[0][0][0] = 0
        dp[0][1][0] = -prices[0]  
        # 只有一支股票  不可能交易1次、2次.....
        for i in range(1, k+1):
            dp[0][0][i] = float('-inf')
            dp[0][1][i] = float('-inf')
        for i in range(1, len(prices)):
            for j in range(0, k+1):
                if j == 0:
                    dp[i][0][0] = 0 
                    dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])
                else:
                    dp[i][0][j] = max(dp[i-1][0][j], dp[i-1][1][j-1]+prices[i])
                    dp[i][1][j] = max(dp[i-1][1][j], dp[i-1][0][j]-prices[i])
        res = float("-inf")
        for i in range(k+1):
            res = max(res, dp[len(prices)-1][0][i])
        return res

        # 2、一维dp
        if len(prices) == 0: return 0
        # dp[j][k]代表某一天持股状态为j，交易次数为K，所获取的最大利润
        # dp[0][k] = max(dp[0][k], dp[1][k-1]+prices[i])
        # dp[1][k] = max(dp[1][k], dp[0][k]-prices[i])
        dp = [[0 for _ in range(k+1)] for _ in range(2)]
        # base case 第一天
        dp[0][0] = 0
        dp[1][0] = -prices[0]  
        # 只有一支股票  不可能交易1次、2次.....
        for i in range(1, k+1):
            dp[0][i] = float('-inf')
            dp[1][i] = float('-inf')
        for i in range(1, len(prices)):
            for j in range(0, k+1):
                if j == 0:
                    dp[0][0] = 0 
                    dp[1][0] = max(dp[1][0], dp[0][0]-prices[i])
                else:
                    dp[0][j] = max(dp[0][j], dp[1][j-1]+prices[i])
                    dp[1][j] = max(dp[1][j], dp[0][j]-prices[i])
        res = float("-inf")
        for i in range(k+1):
            res = max(res, dp[0][i])
        return res

六、子序列子数组问题系列

题目汇总

子数组必须是连续的，子序列不一定要连续的；

674. 最长连续递增子序列

题意：寻找数组中最长连续递增子序列的长度并找到这个子序列打印出来？

674. 最长连续递增序列.

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        # dp[i]表示以i元素结尾的最长连续递增子序列的长度
        dp = [1 for _ in range(len(nums))]
        max_len = 1
        s_end = 1
        for i in range(1, len(nums)):
            # 如果前一个元素小于当前元素 以当前元素结尾的最长子序列长度=以前一个元素结尾的最长子序列长度+1
            # 如果前一个元素大于等于当前元素 则以当前元素结尾的最长子序列长度=1
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
            if dp[i] > max_len:
                max_len = dp[i]
                s_end = i
        # 找到最长连续递增子序列
        # end - start + 1 = len -> start = end - len + 1
        # print(nums[s_end-max_len+1:s_end+1])
        return max_len

300. 最长递增子序列（经典）

题意：寻找数组中最长递增子序列的长度？

300. 最长递增子序列.

视频讲解.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) < 2: return len(nums)
        # dp[i]表示以当前元素为结尾的最长递增子序列长度
        # base case 全部为1 加上每个元素之前都比当前元素大 
        dp = [1 for _ in range(len(nums))]
        max_len = 1
        for i in range(1, len(nums)):
            # 对每个元素都要从前面的元素开始找 找比当前元素小的元素 得到可能的最长子序列长度=dp[j]+1
            # 不确定最长的子序列是哪个  所以要一个个比较
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
            if max_len < dp[i]: max_len = dp[i]
        return max_len

53. 最大子数组和

题意：寻找数组中连续子序列的最大和？

53. 最大子数组和.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        # dp[i]表示以i元素结尾的连续子数组的最大和
        dp = nums
        max_sum = dp[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i], dp[i-1]+nums[i])
            if max_sum < dp[i]:
                max_sum = dp[i]
        return max_sum

152. 乘积最大子数组

题意：寻找数组中连续子序列的最大乘积？

152. 乘积最大子数组.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 这道题和最大子数组和差不多，但是需要考虑一个特殊情况：
        # 当i-1的乘积是个负数，第i个元素也是一个负数的时候 此时乘积可能最大
        # 所以需要定义两个dp数组，一个记录子数组最大乘积、一个记录子数组最小乘积
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        max_mul = nums[0]
        # 以nums[i]元素结尾的子数组的最大乘积
        dp_max = [nums[i] for i in range(len(nums))]
        # 以nums[i]元素结尾的子数组的最小乘积
        dp_min = [nums[i] for i in range(len(nums))]
        for i in range(1, len(nums)):
            # 以nums[i]为结尾的子序列最大乘积有3种情况：
            # 1、以nums[i-1]为结尾的子序列的最大乘积 * nums[i]  比如nums[i]>0  dp_max[i-1]>0
            # 2、以nums[i-1]为结尾的子序列的最小乘积 * nums[i]  比如nums[i]<0  dp_max[i-1]<0
            # 3、就是当前元素一个元素 dp_max[i]
            dp_max[i] = max(dp_max[i], dp_max[i-1]*nums[i], dp_min[i-1]*nums[i])
            # 同理以nums[i]为结尾的子序列最小乘积也有3种情况
            dp_min[i] = min(dp_min[i], dp_max[i-1]*nums[i], dp_min[i-1]*nums[i])
            max_mul = max(dp_max[i], dp_min[i], max_mul)
        return max_mul

1143. 最长公共子序列（经典）

题意：求两个字符串的最长公共子序列（可以不连续）？扩展：怎么找到这个子序列呢（打印出来）？

1143. 最长公共子序列.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2: return 0
        # dp[i][j]表示text1的子集0~i-1 和 text2的子集0~j-1的最长公共子序列的长度
        dp = [[0 for _ in range(len(text2)+1)] for _ in range(len(text1)+1)]  # 0-i  0-j
        max_len = 0
        for i in range(1, len(text1)+1):  # 1-i
            for j in range(1, len(text2)+1):  # 1-j
                if text1[i-1] == text2[j-1]:
                    # 如果当前两个子序列最尾的字符相等
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    # 如果当前长度为i的text1子序列和长度为j的text2子序列最尾的字符不相等  
                    # 并不意味着这两个子序列就没有公共子序列了  
                    # 因为长度为i-1的text1子序列和长度为j的text2子序列可能是有公共子序列了
                    # 长度为i的text1子序列和长度为j-1的text2子序列也可能有公共子序列
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                if dp[i][j] > max_len: max_len = dp[i][j]
        return max_len

718. 最长公共子数组

题意：求两个字符串的最长公共子数组（必须连续），找出来并打印

718. 最长重复子数组.

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        if not nums1 or not nums2: return 0
        # dp[i][j]表示长度为i的nums1子数组和长度为j的nums2子数组的最长公共子数字长度
        dp = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1)]
        max_len = 0
        s_end = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                # 如果当前位置相等 加1  不想等直接为0了 因为子数组需要连续的
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    s_end = i
        # 找到这个最长重复子数组 打印出来
        # print(nums1[s_end-max_len:s_end])
        return max_len

718. 最长公共子数组

题意：求两个字符串的最长公共子数组（必须连续），找出来并打印

718. 最长重复子数组.

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        if not nums1 or not nums2: return 0
        # dp[i][j]表示长度为i的nums1子数组和长度为j的nums2子数组的最长公共子数字长度
        dp = [[0 for _ in range(len(nums2)+1)] for _ in range(len(nums1)+1)]
        max_len = 0
        s_end = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                # 如果当前位置相等 加1  不想等直接为0了 因为子数组需要连续的
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    s_end = i
        # 找到这个最长重复子数组 打印出来
        # print(nums1[s_end-max_len:s_end])
        return max_len

647. 回文子串

题意：字符串中统计回文子串的个数
647. 回文子串.

class Solution:
    def countSubstrings(self, s: str) -> int:
        if len(s) == 1: return 1
        res = 0
        # dp[i][j]表示s[i:j+1]是否是回文串
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        # base case
        for i in range(len(s)):
            dp[i][i] = True
            res += 1
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if j - i < 2: dp[i][j] = True
                    else: dp[i][j] = dp[i+1][j-1]
                if dp[i][j]: res += 1
        return res

5. 最长回文子串（经典）

题意：找到其中一个最长回文子串。提高：找到所有最长回文子串？

5. 最长回文子串.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2: return s
        
        max_len = 1
        s_start, s_end = 0, 0
        # dp[i][j]表示s[i:j+1]是否是回文串
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        # base case
        for i in range(len(s)):
            dp[i][i] = True
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if j - i < 2: dp[i][j] = True
                    else: dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and (j-i+1) > max_len:
                    max_len = j - i + 1
                    s_start = i
                    s_end = j
        # 如果要找到最长所有回文子串
        # res = []
        # if max_len == 1: 
        #     for i in s: res.append(i)
        # for i in range(len(s)):
        #     for j in range(i+1, len(s)):
        #         if dp[i][j] and (j-i+1) == max_len: res.append(s[i:j+1])
        # print(res) 
        
        return s[s_start:s_end+1]  # 找到其中一个最长回文子串

516. 最长回文子序列（经典）

516. 最长回文子序列.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) < 2: return len(s)
        # dp[i][j]表示子串s[i:j+1]内的最长回文子序列的长度
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        max_len = 1
        # base case
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                # 如果首尾相等 左右都往中间压缩+2
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                # 如果首尾不相等 max(左边往右走一格, 右边往左走一格)
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
        return max_len

七、字符串问题系列

在字符串的前面加上空字符之后，会让初始化操作变得简单了很多，类似于哨兵的那种原理。
如果涉及到两个字符串的动规问题，一般都是二维dp

题目汇总

72. 编辑距离

72. 编辑距离.

视频讲解.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if len(word2) == 0: return len(word1)
        if len(word1) == 0: return len(word2)
        # dp[i][j]表示word1[1:i+1]到word2[1:j+1]最少的操作数
        dp = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
        # base case
        for i in range(1, len(word1)+1):
            dp[i][0] = i
        for j in range(1, len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                # dp[i][j]可以由三个方向来：dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]
                # 比如     abc
                #         acd  
                # 此时i->c  j->d
                # 知道ab->acd操作步数为dp[i-1][j]  =>  abc->acd操作数为dp[i-1][j]+1删除c即可 
                # 知道abc->ac操作步数为dp[i][j-1]  =>  abc->acd操作数为dp[i][j-1]+1插入d即可
                # 知道ab->ac操作步数为dp[i-1][j-1] =>  abc->acd操作数为dp[i-1][j-1]+1将c替换为d即可
                else:             #  删除          插入           替换
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
        return dp[-1][-1]

牛客Top200高频：最小编辑代码

题意：和上一题几乎一样，就是换了评价方式

牛客Top200高频：最小编辑代码.

class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        if len(str1) == 0: return len(str2) * ic
        if len(str2) == 0: return len(str1) * ic
        # dp[i][j]表示str1[1:i+1]->str2[1:j+1]的最小代价
        dp = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]
        # base case
        for i in range(len(str1)+1):
            dp[i][0] = i * ic
        for j in range(len(str2)+1):
            dp[0][j] = j * ic
        for i in range(1, len(str1)+1):
            for j in range(1, len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # ac d
                    # bc e
                    dp[i][j] = min(dp[i-1][j]+dc, dp[i][j-1]+ic, dp[i-1][j-1]+rc)
        return dp[-1][-1]

LeetCode583: 两个字符串的删除操作

LeetCode583: 两个字符串的删除操作.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if len(word1) == 0: return len(word2)
        if len(word2) == 0: return len(word1)
        # dp[i][j]代表word1[1:i+1]和word2[1:j+1]相同的最小操作数（只能用删除操作）
        dp = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
        # base case
        for i in range(1, len(word1)+1):
            dp[i][0] = i
        for j in range(1, len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                # abc
                # cde
                # 此时i->c  j->e
                else:       
                    # 已知道ab->cde的最小步数为dp[i-1][j] 现在要求abc->cde的最小步数 显然=dp[i-1][j]+1 wode1直接删除c即可
                    # 已知道abc->cd的最小步数为dp[i][j-1] 现在要求abc->cde的最小步数，显然dp[i][j-1]+1 wode2直接删除e即可
                    
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]

LeetCode32. 最长有效括号（难）

32. 最长有效括号.

视频讲解.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) == 0: return 0
        max_len = 0
        # dp[i]代表s[:i+1]中有效括号的长度
        dp = [0 for _ in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == '(': dp[i] = 0
            else:
                if s[i-1] == '(' : dp[i] = dp[i-2] + 2
                #  注意这里需要保证(i-dp[i-1]-1)>=0因为如果小于0就会跑到最后的元素了
                # (i-dp[i-1]-2)不需要保证，因为默认是为0的，for从前往后遍历 如果(i-dp[i-1]-2)<0 那么dp[(i-dp[i-1]-2)]刚好等于0 对结果不影响
                elif s[i-dp[i-1]-1] == '(' and (i-dp[i-1]-1)>=0:
                    dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
            if dp[i] > max_len: max_len = dp[i]
        return max_len

圆环回原点问题（待更新）

字节的高频面试题目

问题描述：

圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。

输入: 2
输出: 2
解释: 两种方案。分别是0->1->0和0->9->0

Reference

算法刷题重温(八): 硬核动态规划.

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2022-03-22 20:49:54 更:2022-03-22 20:52:51

360图书馆购物三丰科技阅读网日历万年历 2025年1日历

-2025/1/9 2:09:54-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码

[数据结构与算法]【Leetcode 动态规划专题】

目录

一、一般问题系列

1.1、题目汇总

leetcode 509. 斐波那契数

leetcode 70. 爬楼梯

leetcode 343. 整数拆分

剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫环问题 难 地推公式没懂）

二、路径规划系列

2.1、题目汇总

leetcode 62. 不同路径

leetcode 63. 不同路径 II

leetcode 64. 最小路径和

三、背包系列

3.1、0-1背包问题

解题思路

题目汇总

416. 分割等和子集

494. 目标和

3.2、完全背包问题

题目汇总

518. 零钱兑换 II

322. 零钱兑换

四、打家劫舍系列

198. 打家劫舍

213. 打家劫舍 II

五、股票问题系列

121. 买卖股票的最佳时机

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

309. 最佳买卖股票时机含冷冻期（包含I、II 代码通过了但是有疑问？？？）

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

188. 买卖股票的最佳时机 IV（包含III）

六、子序列子数组问题系列

题目汇总

674. 最长连续递增子序列

300. 最长递增子序列（经典）

53. 最大子数组和

152. 乘积最大子数组

1143. 最长公共子序列（经典）

718. 最长公共子数组

718. 最长公共子数组

647. 回文子串

5. 最长回文子串（经典）

516. 最长回文子序列（经典）

七、字符串问题系列

题目汇总

72. 编辑距离

牛客Top200高频：最小编辑代码

LeetCode583: 两个字符串的删除操作

LeetCode32. 最长有效括号（难）

圆环回原点问题（待更新）

Reference

剑指 Offer 62. 圆圈中最后剩下的数字（约瑟夫环问题难地推公式没懂）