06.动态规划

动态规划（DP）是一种通过分解问题、保存中间结果来避免重复计算的优化方法

动态规划算法将待求解问题拆分成一系列相互交叠的子问题
通过递推关系定义各子问题的求解策略，并随时记录子问题的解
最终获得原始问题的解，避免了对交叠子问题的重复求解

# 01.线性 DP 模型

特点：通常用于求解一个数组或序列的最优解
状态定义：dp[i] 表示从数组 nums 开头到 nums[i] 这个位置，最长的严格递增子序列的长度
状态转移方程： dp[i] = max(dp[i], dp[j] + 1) （条件 nums[j] < nums[i]）
初始状态：dp 数组初始为 [1, 1, 1, 1, 1, 1, 1, 1]，表示每个元素单独作为一个子序列的长度为1

# 1、最长递增子序列

300.最长递增子序列 (opens new window)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

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

1
2
3

# 2、python

状态定义：dp[i] 表示从数组 nums 开头到 nums[i] 这个位置，最长的严格递增子序列的长度
状态转移方程： dp[i] = max(dp[i], dp[j] + 1) （条件 nums[j] < nums[i]）
初始状态：dp 数组初始为 [1, 1, 1, 1, 1, 1, 1, 1]，表示每个元素单独作为一个子序列的长度为1
通过逐步更新 dp 数组，最终 dp 变成 [1, 1, 1, 2, 2, 3, 4, 4]，因此最长递增子序列的长度为 4

class Solution:
    def lengthOfLIS(self, nums):
        dp = [1] * len(nums)           # 初始化 每个元素单独作为一个子序列的长度为1
        for i in range(1, len(nums)):  # 每次都比较 0~i-1的值与 nums[i]比较
            for j in range(i):
                if nums[i] > nums[j]:  # nums[i]更大 代表 可以接在 nums[j] 后面
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)     # 返回 dp 数组中的最大值，即为最长递增子序列的长度


print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出: 4

1
2
3
4
5
6
7
8
9
10
11
12

如何更新dp[i]:
- 我们想要找到 nums[i] 之前的元素中所有比 nums[i] 小的元素 nums[j]（其中 j < i）
- 如果 nums[j] < nums[i]，那么 dp[i] 可以更新为 dp[i] = max(dp[i], dp[j] + 1)
- 表示 nums[i] 可以接在 nums[j] 后面（遍历0~i-1 多有数据即可知道接在哪里最长）

# 02.双序列 DP 模型

特点：处理两个序列之间的关系，常用于求解序列匹配、编辑距离等问题

# 1、最长公共子序列

1143.最长公共子序列 (opens new window)
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度
如果不存在 公共子序列 ，返回 0
由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

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

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0

1
2
3
4
5
6
7

# 2、python

状态定义：dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度
状态转移方程：
- 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符匹配，公共子序列长度加 1
- 如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示字符不匹配，选择之前的较长子序列
初始状态：
- 创建一个大小为 (m+1) x (n+1) 的二维数组 dp，其中所有元素初始化为 0
- 因为空字符串与任何字符串的最长公共子序列长度都是 0，这个数组用于存储子问题的解

时间复杂度: O(m * n)

空间复杂度: O(m * n) 二维数组来存储中间结果

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    # dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):         # i指针遍历 text1 字符串
        for j in range(1, n + 1):     # j指针遍历 text2 字符串
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1   # 如果当前字符相同，取前一状态（对角线）的值加 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    # 如果当前字符不同，取 dp[i-1][j] 和 dp[i][j-1] 中的最大值

    return dp[m][n]    # 最终结果位于 dp[m][n]，即为最长公共子序列的长度

print(longestCommonSubsequence("abcde", "ace"))  # 输出: 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 3、推演结果

下面是以 text1 = "abcde" 和 text2 = "ace" 为例，按照类似格式展示 dp 数组的构建过程
状态定义：dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度
状态转移方程：
- 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符匹配，公共子序列长度加 1
- 如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示字符不匹配，选择之前的较长子序列
初始状态：dp[i][0] = 0 和 dp[0][j] = 0，因为空字符串与任何字符串的最长公共子序列长度都是 0

# 03.背包问题

有一个背包，其最大承重为 W，有 n 个物品，每个物品有一个重量 w[i] 和一个价值 v[i]

目标是选择一些物品放入背包中，使得背包中的物品总重量不超过 W，并且这些物品的总价值最大化

# 1、零钱兑换

322.零钱兑换 (opens new window)
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额
计算并返回可以凑成总金额所需的 最少的硬币个数
如果没有任何一种硬币组合能组成总金额，返回 -1
你可以认为每种硬币的数量是无限的

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

1
2
3
4
5
6
7
8
9

# 2、python

状态定义：我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数
状态转移方程： dp[i] = min(dp[i], dp[i - coin] + 1)
- dp[i - coin] 复用i - coin 所在位置中计算的最小数量，加上当前硬币，就是当前硬币 i位置最小数量
初始状态：[0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
- 初始时所有金额都不可能被凑出，金额为 0 时，不需要任何硬币

class Solution:
    def coinChange(self, coins, amount):
        # 初始化 dp 数组，长度为 amount + 1，所有值初始为 amount + 1（表示一个不可能达到的值）
        dp = [amount + 1] * (amount + 1)

        dp[0] = 0  # 当金额为 0 时，所需硬币数为 0
        for i in range(1, amount + 1):  # 遍历从 1 到 amount 的所有金额
            for coin in coins:  # 对于每个金额，遍历所有硬币面值
                if i >= coin:  # 硬币大于当前 i 位置索引不进入循环
                    dp[i] = min(dp[i], dp[i - coin] + 1)  # 更新 dp[i]，取最小值

        # 如果 dp[amount] 仍然为初始值，说明无法凑出这个金额，返回 -1
        return dp[-1] if dp[-1] != amount + 1 else -1

print( Solution().coinChange([1, 2, 5], 11) )  # 输出: 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 3、推演结果

状态定义：我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数
状态转移方程： dp[i] = min(dp[i], dp[i - coin] + 1)
- dp[i - coin] 复用i - coin 所在位置中计算的最小数量，加上当前硬币，就是当前硬币 i位置最小数量
初始状态：[0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
- 初始时所有金额都不可能被凑出，金额为 0 时，不需要任何硬币
硬币：[1, 2, 5] 目标金额：11

金额 | dp[金额] |  硬币组合
-----|----------|------------
  0  |    0     |  []
  1  |    1     |  [1]
  2  |    1     |  [2]
  3  |    2     |  [1, 2]
  4  |    2     |  [2, 2]
  5  |    1     |  [5]
  6  |    2     |  [1, 5] 或 [1, 2, 2]
  7  |    2     |  [2, 5]
  8  |    3     |  [1, 2, 5] 或 [1, 1, 2, 2, 2]
  9  |    3     |  [2, 2, 5]
 10  |    2     |  [5, 5]
 11  |    3     |  [1, 5, 5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

金额：i = 2 dp[2]初始化值为12

# 第 1 次迭代 (i = 1)
硬币 1：更新 dp[1] = min(dp[1], dp[1 - 1] + 1) => dp[1] = 1
结果：[0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
# i= 1小于硬币 2和5，所以 i >= coin 条件不成立

# 第 2 次迭代 (i = 2)
硬币 1：更新 dp[2] = min(dp[2], dp[2 - 1] + 1) => dp[2] = 2
硬币 2：更新 dp[2] = min(dp[2], dp[2 - 2] + 1) => dp[2] = 1
结果：[0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]

1
2
3
4
5
6
7
8
9

# dp[i] = min(dp[i], dp[i - coin] + 1) 
# dp[i - coin] 复用 i - coin 所在位置中计算的最小数量，加上当前硬币，就是当前硬币 i位置最小数量

1
2

上次更新: 2024/10/15 16:27:13

← 05.回溯算法 01.数组→