动态规划 典型例题

总结

动态规划的的四个解题步骤是：

• 定义子问题
• 写出子问题的递推关系
• 确定 DP 数组的计算顺序
• 空间优化（可选）

from functools import cache
@cache #缓存，避免重复运算
def dfs(i)->int:
	if 终止: return 0 #具体返回什么值要看题目的含义
	cnt = 0
    for 递归方向:
        cnt += dfs(xxx) #如果是计数，一般是叠加，也有可能是取最大或者最小
    return cnt

509 F 数列

注意：

f0 = 0, f1 = 0, f2 = 1

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n

        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p, q = q, r
            r = p + q
        
        return r

198 打家劫舍

class Solution:
    def rob(self, nums: List[int]) -> int:

        N = len(nums)
        dp = [0] * (N + 1)
        # dp[i]  [0, i) 家里面能偷得的最大金额
        dp[0] = 0
        dp[1] = nums[0]
        for k in range(2, N + 1):
            dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2]);
        return dp[N]

64 最小路径和

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, columns = len(grid), len(grid[0])
        # 注意可以这样初始化
        dp = [[0] * columns for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, columns):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, columns):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[rows - 1][columns - 1]

62 不同路径

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = f[i - 1][j] + f[i][j - 1]
        return f[m - 1][n - 1]

63 有障碍物的不同路径

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        dp = [[0] * n for _ in range(m)]

        if obstacleGrid[0][0] != 1:
            dp[0][0] = 1

        # 给第一行赋值
        for i in range(1, n):
            if obstacleGrid[0][i] != 1:
                dp[0][i] = dp[0][i - 1]

        # 给第一列赋值
        for j in range(1, m):
            if obstacleGrid[j][0] != 1:
                dp[j][0] = dp[j - 1][0]

        for i in range(1, m):
            for j in range(1, n):
                # 关键判断
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m - 1][n - 1]

118 杨辉三角

行号从 1 开始，列从 0 开始

class Solution:
    def generate(self, numRows):
        # f[i][j]: 第 i 行第 j 个元素的值
        # f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
        # 注意给边界赋值
        dp = []
        dp.append([1])
        
        # numRows > 1
        for i in range(1, numRows):
            dp.append([0] * (i + 1))
            for j in range(i + 1):
                if j == 0 or j == i:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

        return dp

120 杨辉三角的变体

class Solution:
    def minimumTotal(self, triangle):
        # f[i][j] : 到达第 i 行 j 个元素的最小路径
        # f = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
        # 边界只能累加

        m = len(triangle)
        dp = [triangle[0]]

        # 类似杨辉
        # 行列都是从 0 开始计数
        for i in range(1, m):
            dp.append([0] * (i + 1))
            for j in range(i + 1):
                if j == 0:
                    dp[i][j] = dp[i - 1][j] + triangle[i][j]
                elif j == i:
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

        # 找到最下面一行的最小值
        ans = float('inf')
        for i in range(m):
            ans = min(ans, dp[m - 1][i])

        return ans

279 完全平方数

import math

class Solution:
    def numSquares(self, n: int) -> int:
        """
        求 f(n): 和为 n 的完全平方数的最少数量 
        f(n) = f(n - j ^ 2) + 1
        j^2 <= n

        f(1) = 1
        f(2) = f(2 - 1) + 1 = 2
        f(3) = min(f(3 - 1)) + 1 = 3;
        f(4) = f(0) + 1 or f(3) + 1
        """

        # 初始化动态规划数组，储存和为 i 的最少完全平方数数量
        # 数值范围 1 -- n
        dp = [0] * (n + 1)
        dp[1] = 1  # 初始条件，和为 1 的最少数量为 1

        # 遍历计算从 2 到 n 的和为 i 的最少完全平方数数量
        for i in range(2, n + 1):
            s = int(math.sqrt(i))  # 计算 i 的平方根，作为循环的上界
            ans = float('inf')  # 初始化 ans 为正无穷，用于记录最小数量
            for j in range(s, 0, -1):
                ans = min(ans, dp[i - j * j] + 1)  # 更新最小数量
            dp[i] = ans  # 记录和为 i 的最小数量

        return dp[n]  # 返回和为 n 的最小完全平方数数量

377 组合总和

不需要去重

class Solution:
    def combinationSum4(self, nums, target):
        """
        f[i] = nums 中可以组合为 i 的元素组合的个数
        f[i] = Σf[i - nums[j]]
        初始化为1
        """
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(1, target + 1):
            for num in nums:
                if num <= i and dp[i] < float('inf') - dp[i - num]:
                    dp[i] += dp[i - num]

        return dp[target]

300 最长递增子序列*

以下标 i 的元素结尾的最长递增子序列的长度

class Solution:
    def lengthOfLIS(self, nums):
        """
        dp[i] 以下标为 i 的数结尾的最长递增子序列的长度
        """
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

674 最长连续递增子序列*

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:

        dp = [0] * len(nums)
        ans = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + 1
                ans = max(ans, dp[i])
        return ans

718 最长公共子串

class Solution:
    def findLength(self, nums1, nums2):
        """
        f(i, j) 包含 nums1 的第 i 个数字和包含 nums2 的第 j 个数字的最长重复子数组的长度
        if nums1[i] == nums2[j]
            f(i, j) = f(i - 1, j - 1) + 1
        else:
            f(i, j) = 0
        """

        # 第一行和第一列表示不取任何数字
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]

        ans = 0
        # 遍历行
        for i in range(1, len(nums1) + 1):
            # 遍历列
            for j in range(1, len(nums2) + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                # 肯定不是最长公共子串
                else:
                    dp[i][j] = 0
                ans = max(ans, dp[i][j])
        return ans

1143 最长公共子序列

可以不连续，所以else后面有差异

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1)
        len2 = len(text2)

        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        
        return dp[len1][len2]

583 两个字符串的删除操作

class Solution:
    def minDistance(self, word1, word2):
        """
        f(i, j) 将 s1 的前 i 个字符和 s2 的前 j 个字符变为相同的最小操作数

        if s1[i] == s2[j]
            f[i - 1, j - 1]
        else
            min (f[i - 1, j], f[i, j - 1]) + 1
        f[0, j] = j
        f[i, 0] = i
        """

        len1 = len(word1)
        len2 = len(word2)

        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

        for j in range(len2 + 1):
            dp[0][j] = j
        for i in range(len1 + 1):
            dp[i][0] = i

        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[len1][len2]

72 编辑距离

大体和上一题类似，操作有三种

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        """
        f(i, j) : word1 的前 i 个转到 word2 的前 j 个

        插入
        f(i, j) = f(i, j - 1) + 1

        删除
        f(i, j) = f(i - 1, j) + 1

        替换
        f(i, j) = f(i - 1, j - 1) + 1

        相等
        f(i, j) = f(i - 1, j - 1)

        f(0, j) = j
        f(i, 0) = i
        """

        len1 = len(word1)
        len2 = len(word2)

        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

        for i in range(len1 + 1):
            dp[i][0] = i
        for i in range(len2 + 1):
            dp[0][i] = i

        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1

        return dp[len1][len2]

647 回文子串

考虑子串长度

1个

2个

3个及以上

class Solution:
    def countSubstrings(self, s: str) -> int:
        """
        f(i, j) i 到 j 的子串是否为回文串 0 -- n - 1
            1. s[i] = s[j] && f(i + 1, j - 1)
            i + 1 <= j - 1 ==> i + 2 <= j

            2. 单独算 i + 1 = j, i = j
        """

        n = len(s)
        cnt = 0

        dp = [[False] * n for _ in range(n)]
        for j in range(n):
            for i in range(j, -1, -1):
                # base case
                # 只有一个字符
                if i == j:
                    dp[i][j] = True
                elif i + 1 == j:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]

                if dp[i][j] == True:
                    cnt += 1

        return cnt

516 最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        len_s = len(s)
        dp = [[0] * len_s for _ in range(len_s)]

        for j in range(len_s):
            for i in range(j, -1, -1):
                if i == j:
                    dp[i][j] = 1
                elif i + 1 == j:
                    dp[i][j] = 2 if s[i] == s[j] else 1
                else:
                    if s[i] == s[j]:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return dp[0][len_s - 1]

416 0-1 背包 分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 求和
        total_sum = sum(nums)

        if total_sum % 2 == 1:
            return False

        target = total_sum // 2

        # 能否凑出半个 0-1 背包
        # 考虑前 i 个数字能否凑出 j
        # f(i, j) = f(i - 1, j) or f(i - 1, j - nums[i])
        # base case: f(0, j): f(0, 0) = True

        dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]
        dp[0][0] = True

        # 从前 i 个数开始
        for i in range(1, len(nums) + 1):
            for j in range(target + 1):
                if nums[i - 1] <= j:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
                else:
                    # 如果不选
                    dp[i][j] = dp[i - 1][j]

        return dp[len(nums)][target]

优化

第一个维度删掉，第二个反过来

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 求和
        total_sum = sum(nums)

        if total_sum % 2 == 1:
            return False

        target = total_sum // 2

        # 能否凑出半个 0-1 背包

        # 考虑前 i 个数字能否凑出 j
        # f(i, j) = f(i - 1, j) or f(i - 1, j - nums[i])
        # base case: f(0, j): f(0, 0) = True

        # 优化
        # 删除第一个维度，第二层反过来
        dp = [False] * (target + 1)
        dp[0] = True

        # 从前 i 个数开始
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 求和
        total_sum = sum(nums)

        if total_sum % 2 == 1:
            return False

        target = total_sum // 2

        # 能否凑出半个 0-1 背包
        # 考虑前 i 个数字能否凑出 j
        # f(i, j) = f(i - 1, j) or f(i - 1, j - nums[i])
        # base case: f(0, j): f(0, 0) = True

        dp = [False] * (target + 1)
        dp[0] = True

        # 从前 i 个数开始
        for i in range(1, len(nums) + 1):
            for j in range(target, nums[i - 1] - 1, -1):
                    dp[j] = dp[j] or dp[j - nums[i - 1]]


        return dp[target]

494 目标和

pos - (sum - pos) = target

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)

        if (total_sum + target) % 2 == 1 or total_sum + target < 0:
            return 0

        pos = (total_sum + target) // 2

        """
        f(i, j) 考虑前 i 个数字，凑出 j 有多少种方案
        f(i, j) = f(i-1, j) + f(i-1, j-nums[i])
        f(0, 0) = 1, f(0, j) = 1
        """
        n = len(nums)
        # dp = [[0] * (pos + 1) for _ in range(n + 1)]
        # # 没有数字
        # dp[0][0] = 1

        # for i in range(1, n + 1):
        #     for j in range(pos + 1):
        #         if nums[i - 1] <= j:
        #             dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]
        #         else:
        #             dp[i][j] = dp[i - 1][j]
        # return dp[n][pos]

        dp = [0] * (pos + 1) 
        # 没有数字
        dp[0] = 1

        for i in range(1, n + 1):
            for j in range(pos, nums[i - 1] - 1, -1):
                dp[j] = dp[j] + dp[j - nums[i - 1]]
  
        return dp[pos]

474 一和零 0-1 三维-->二维

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        length = len(strs)
        # 开两个背包的容量
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        """
        前 i 个字符串最多 j 个 0 和 k 个 1，可以选的最多字符串数量
        f(i,j,k) = max(f(i - 1, j, k), f(i - 1, j - zero, k - one) + 1)
        f(0, j, k) = 0

        0-1 逆序
        """

        for i in range(1, length + 1):
            # 统计字符串的数量
            zero, one = 0, 0
            for c in strs[i - 1]:
                if c == '0':
                    zero += 1
                else:
                    one += 1
            # 逆序
            for j in range(m, zero - 1, -1):
                for k in range(n, one - 1, -1):
                    dp[j][k] = max(dp[j][k], dp[j - zero][k - one] + 1)

        return dp[m][n]

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        length = len(strs)
        # 开两个背包的容量
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        """
        前 i 个字符串最多 j 个 0 和 k 个 1，可以选的最多字符串数量
        f(i,j,k) = max(f(i - 1, j, k), f(i - 1, j - zero, k - one) + 1)
        f(0, j, k) = 0

        0-1 逆序
        """

        for i in range(1, length + 1):
            zero, one = 0, 0
            for c in strs[i - 1]:
                if c == '0':
                    zero += 1
                else:
                    one += 1

            for j in range(m, zero - 1, -1):
                for i in range(n, one - 1, -1):
                    dp[j][i] = max(dp[j][i], dp[j - zero][i - one] + 1)
        return dp[m][n]

322 零钱兑换 完全背包

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        前 i 个硬币凑出 amount 的最小数量
        f(i, j) = min(f(i - 1, j), f(i - 1, j - coins[i - 1]) + 1)
        f(0, j) f(0, 0) = 0 else = inf
        """
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for j in range(1, amount + 1):
            dp[0][j] = 10010

        for i in range(1, n + 1):
            for j in range(0, amount + 1):
                if coins[i - 1] <= j:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
                else:
                    dp[i][j] = dp[i - 1][j]
                

        return -1 if dp[n][amount] > amount else dp[n][amount]

正序

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        """
        前 i 个硬币凑出 amount 的最小数量
        f(i, j) = min(f(i - 1, j), f(i - 1, j - coins[i - 1]) + 1)
        f(0, j) f(0, 0) = 0 else = inf
        """
        n = len(coins)
        dp = [0] * (amount + 1)
        dp[0] = 0
        for j in range(1, amount + 1):
            dp[j] = 10010

        for i in range(1, n + 1):
            for j in range(0, amount + 1):
                if coins[i - 1] <= j:
                    dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1)

                

        return -1 if dp[amount] > amount else dp[amount]

518 零钱兑换

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # f(i,j) 考虑前 i 个硬币，凑出 j 有多少种方案？
        # f(i-1, j) + f(i, j-coins[i-1]) 完全背包

        n = len(coins)
        dp = [0] * (amount + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            for j in range(coins[i - 1], amount + 1):
                dp[j] += dp[j - coins[i - 1]]
        return dp[amount]