动态规划算法专题探究

目录

第一章：动态规划算法理论基础

1.1动态规划概述

动态规划（Dynamic Programming）是一种解决复杂问题的优化方法，常用于求解具有重叠子问题和最优子结构特征的问题。它将原始问题分解为一系列相互依赖的子问题，并通过保存每个子问题的解来避免重复计算，从而提高算法的效率。

动态规划的核心思想是“最优子结构”，即整个问题的最优解可以通过子问题的最优解来构造。动态规划的关键在于合理定义状态和状态转移方程，以及正确处理边界情况和初始条件。

动态规划广泛应用于各个领域，例如最短路径问题、背包问题、字符串编辑距离等。它能够有效地降低问题的时间复杂度，提高算法的效率，但在实际应用中需要注意空间复杂度的控制和边界条件的处理。

​​​​​​​1.2动态规划的解题步骤

动态规划的解题步骤可以综合为以下五个关键步骤：

①确定dp数组以及下标的含义：确定dp数组的大小和定义，以及每个下标所表示的含义。dp数组是用来存储子问题的解的数组，通过合理定义dp数组的含义，可以将原问题划分为若干个子问题。

②确定递推公式：根据原问题和子问题之间的关系，找到递推公式。递推公式描述了子问题的最优解是如何从已知的子问题的最优解得到的。

③dp数组的初始化：确定dp数组的初始值，即最简单的子问题的解。通常情况下，可以根据实际问题的特点设置初始值。有时候需要特殊处理一些边界情况。

④确定遍历顺序：确定计算dp数组的遍历顺序。遍历顺序应该保证在计算当前状态时，所依赖的所有状态都已经计算过。常见的遍历顺序有自顶向下（递归+记忆化搜索）和自底向上（迭代）两种方式。

⑤举例推导dp数组：通过具体的例子来推导和验证dp数组的计算过程。可以手动模拟计算dp数组，看是否能够得到正确的结果。

在确定dp数组和递推公式时，需要深入理解问题的本质和规律。

​​​​​​​1.3动态规划算法与贪心算法

动态规划算法（Dynamic Programming）和贪心算法（Greedy Algorithm）都是常用的解决优化问题的算法，它们在一些情况下有相似之处，但也有明显的区别。

（1）相似之处：

①都是通过将大问题划分为子问题来求解的。

②都需要确定状态转移方程或者选择策略。

③都依赖于最优子结构性质，即当前问题的最优解可以由子问题的最优解得到。

（2）不同之处：

①动态规划算法通常用于求解具有最优子结构的问题，即全局最优解可以通过局部最优解推导得到。而贪心算法通常用于求解具有贪心选择性质的问题，即每一步都采取当前最优的选择，希望最终能够得到全局最优解。

动态规划算法通常需要存储子问题的解，并根据子问题的解来推导出更大规模问题的解。而贪心算法通常只需要存储当前的最优解，不需要回溯或者保存其他子问题的解。

②动态规划算法可以解决一些无法使用贪心算法求解的问题，因为动态规划算法考虑了所有可能的选择和路径，保证了求解的准确性。而贪心算法有时会做出局部最优选择，从而无法得到全局最优解。

③动态规划算法的时间复杂度通常较高，取决于子问题的数量和规模。而贪心算法通常具有较低的时间复杂度，并且往往可以在线性时间内求解。

​​​​​​​1.4算法报告架构

本篇报告分为三个部分。第一部分介绍了动态规划算法的理论基础，为后续解题提供了必要的理论支撑。第二部分是动态规划算法的实战应用，针对多种题型进行了求解，并详细给出了每种题型的求解思路和对应题目的源码实现。第三部分是对第二部分的总结，包括总结出的解题模版以及解题过程中的感悟和收获。

最后对本次专题实验做出了总结。

第二章：动态规划算法实战之背包问题

2.1 0-1背包问题

2.1.1题目：分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

2.1.1 算法设计思路

我们可以将问题转化为背包问题，即在给定一定容量的背包情况下，尽可能装入物品使得背包中物品的总价值最大化。代入0-1背包问题的四点要素如下：

·背包的体积为sum / 2

·背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值

·背包如果正好装满，说明找到了总和为 sum / 2 的子集。

·背包中每一个元素是不可重复放入。

然后利用动态规划的算法步骤进行算法设计。

1.首先，计算数组的元素和sum，如果sum是奇数，则无法分割成两个相等和的子集，直接返回False。

2.创建一个二维数组dp，其中dp[i][j]表示在前i个元素中能否找到和为j的子集。

3.初始化dp数组，对于第一行来说，dp[0][j]都为False，因为没有元素可选。对于第一列来说，dp[i][0]都为True，因为可以选择不装任何元素。

4.对于每个元素nums[i]，遍历背包容量j，如果当前元素nums[i]小于等于背包容量j，则有两种选择：装入或不装入。

①如果选择装入，那么dp[i][j]的值取决于前i-1个元素是否能够凑出总和为j-nums[i]的子集，即dp[i-1][j-nums[i]]。

②如果选择不装入，那么dp[i][j]的值取决于前i-1个元素是否能够凑出总和为j的子集，即dp[i-1][j]。

综合两种情况，只要其中一种情况成立，即dp[i][j]为True。

1. 最终，如果dp[n][target]为True，其中n为数组长度，target为sum的一半，则表示可以将数组分割成两个相等和的子集，返回True；否则，返回False。

2.1.2 程序实现

本次专题实验中的程序实现部分，我采用的都是python语言进行实现。

def canPartition(nums):
    n = len(nums)
    if n < 2:
        return False
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
 
    target = total_sum // 2
    dp = [[False] * (target + 1) for _ in range(n)]
    if nums[0] <= target:
        dp[0][nums[0]] = True
 
    for i in range(1, n):
        for j in range(target + 1):
            dp[i][j] = dp[i-1][j]
            if nums[i] == j:
                dp[i][j] = True
                continue
            if nums[i] < j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
 
    return dp[n-1][target]
 
# 示例测试
nums = [1, 5, 11, 5]
result = canPartition(nums)
print(result)  # 输出：True

2.1.3 算法分析

1. 算法原理阐述：给定一个非空数组nums，我们需要判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。为了解决这个问题，我们可以将其转化为0-1背包问题。将数组的元素视为物品，数组中的每个元素既是物品的重量，也是物品的价值。目标是找到一种装入背包的方式，使得背包的重量恰好等于sum/2（sum为数组元素的总和），并且背包中的物品价值最大。

（2）时间复杂度分析：O(n * target)，其中n是输入数组的长度，target是数组元素和的一半。遍历所有物品和背包容量，时间复杂度为O(n * target)。

（3）空间复杂度分析：O(target)，需要一个大小为target + 1的dp数组来存储状态。

（4）算法正确性分析

通过将分割等和子集问题转化为0-1背包问题，使用动态规划的思想，遍历每个元素，确定是否装入背包，最后根据dp数组的结果判断是否能够分割成两个相等和的子集。算法的正确性可以通过数学归纳法证明。

2.1.4 算法总结

本题是我从力扣上选取的一道关于动态规划算法的经典题，我们将其转化为了0-1背包问题进行了求解。01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。在算法实现过程中，我们首先创建dp数组并对其进行初始化，然后对每个元素都遍历一次背包容量，对装入或不装入作出讨论，得到对应的递推公式。最后得到结果。

2.2 完全背包问题

2.2.1 题目：完全平方数

给你一个整数n，返回和为n的完全平方数的最少数量 。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。

2.2.1 算法设计思路

首先将这个问题代入到完全背包问题中时，可以把完全平方数看作是“物品”，而要凑成的正整数n看作是“背包”的容量。目标是找到和为n的完全平方数的最少数量，这就转化为了在限制条件下求解如何使用完全平方数这些“物品”来填满“背包”。

对于完全背包问题，通常采用动态规划的方法来解决。首先定义一个dp数组，其中dp[j]表示和为j的完全平方数的最少数量。然后根据完全背包问题的特性，采用类似背包问题的动态规划思路来填充这个dp数组。

1.首先确定dp数组以及下标的含义：

dp[j]：和为j的完全平方数的最少数量为dp[j]

2.确定递推公式：

①对于每个j，我们可以通过遍历所有小于等于j的完全平方数i*i，用

dp[j - i * i] + 1来更新dp[j]，并选择最小值。

②具体而言，递推公式为：dp[j] = min(dp[j - i * i] + 1, dp[j])

1. dp数组初始化：

①dp[0]表示和为0的完全平方数的最小数量，所以初始化为0。

②对于非0下标的dp[j]，我们需要将其初始化为一个较大的值，以便在递推的过程中选择最小值。此处将初始化为一个较大值是因为递推公式dp[j] = min(dp[j - i * i] + 1, dp[j])中可以很明显的看出每次dp[i]都是选两项中的最小值，所以只有初始化为最大值时，dp[i]在递推时才不会被覆盖。

4.确定遍历顺序：

我选择外层for遍历背包，内层for遍历物品，其实分析后我认为外层for遍历物品，内层for遍历背包，也是可以的。此部分将在实验讨论中详细分析。

5.推导dp数组：

根据上述内容，我使用动态规划的方法，从dp[0]开始逐步计算dp[1]、dp[2]、...、dp[n]，直到达到目标值n。

根据以上算法设计思路，可以编写代码来解决完全背包问题中的完全平方数问题。

2.2.2 程序实现

def numSquares(n):
    # 初始化dp数组，将其所有元素初始化为无穷大（表示不可能达到的状态）
    dp = [float('inf')] * (n + 1)
    # 设置初始条件：和为0时，需要0个完全平方数
    dp[0] = 0
 
    # 遍历背包容量
    for i in range(1, n + 1):
        # 遍历物品（完全平方数）
        for j in range(1, int(i**0.5)+1):
            # 更新dp数组的值
            dp[i] = min(dp[i], dp[i - j*j] + 1)
 
    return dp[n]
# 测试用例1
n = 12
print(numSquares(n))  # 输出：3
 
# 测试用例2
n = 13
print(numSquares(n))  # 输出：2
 
# 测试用例3
n = 16
print(numSquares(n))  # 输出：1

2.2.3 算法分析

1.时间复杂度与空间复杂度分析

在上述算法中，我使用了两层循环。外层循环遍历了背包容量，从1到n，内层循环遍历了完全平方数，从1到sqrt(n)。对于每个背包容量j，内层循环的次数最多为sqrt(j)。因此，总的时间复杂度可以表

T(n) = 1 + 2 + 3 + ... + sqrt(n)

根据等差数列求和公式，上述时间复杂度可以简化为：

T(n) = (sqrt(n) * (sqrt(n) + 1)) / 2

所以，该算法的时间复杂度为O(sqrt(n)^2)，即O(n)。

空间复杂度方面，我们只使用了一个长度为n+1的dp数组来存储中间结果，所以空间复杂度是O(n)。

1. 算法正确性分析

根据动态规划的思想，我们通过填充dp数组来得到和为n的完全平方数的最小数量。我们通过遍历所有小于等于j的完全平方数ii，用dp[j-ii]+1来更新dp[j]，并选择最小值。在计算过程中，我们不断地更新dp数组，直到得到dp[n]的最优解。因此，算法是正确的。

2.2.4 算法总结

本题是我从力扣上选取的一道适用完全背包模型解决的算法题。在本题中，我们将完全平方数看作是“物品”，而要凑成的正整数n看作是“背包”的容量，目标是找到和为n的完全平方数的最少数量。通过动态规划的方法，我们可以先定义一个dp数组来储存中间结果，然后根据完全背包问题的特性，采用背包问题的动态规划思路来填充这个dp数组。具体而言，我们需要遍历所有小于等于j的完全平方数i*i，使用dp[j - i * i] + 1来更新dp[j]，并选择最小值。最后返回dp[n]即可得到答案。该算法时间复杂度为O(n)，空间复杂度为O(n)。

第三章：动态规划算法实战之打劫、股票问题

3.1 打家劫舍系列问题

3.1.1 题目：打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

3.1.2 算法设计思路

可按照动态规划算法的步骤进行算法设计。

1.确定dp数组以及下标的含义：

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2.确定递推公式：

考虑第i个房间偷或者不偷的情况：

①如果偷第i个房间，那么dp[i] = dp[i - 2] + nums[i]；

②如果不偷第i个房间，那么dp[i] = dp[i - 1]；

综合考虑两种情况，取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])。

1. dp数组初始化：

根据递推公式，初始化dp[0] 和 dp[1]：

dp[0] = nums[0]；

dp[1] = max(nums[0], nums[1])。

4.确定遍历顺序：

由于dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，因此需要从前到后遍历。

5.举例推导dp数组：

根据已给的nums数组，通过循环计算得到dp数组，最终dp[nums.size()-1]的值即为答案。

在具体实现时，需要注意处理成环的情况，即首尾元素不能同时被偷的情况。可以将问题转化为如下两个子问题

①考虑包含首元素，不包含尾元素

②考虑包含尾元素，不包含首元素

然后取两种情况的最大值作为最终结果。

3.1.3 程序实现

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    elif n == 2:
        return max(nums[0], nums[1])
 
    # 考虑不偷窃第一个房屋的情况
    dp1 = [0] * n
    dp1[0] = 0
    dp1[1] = nums[1]
    for i in range(2, n):
        dp1[i] = max(dp1[i - 2] + nums[i], dp1[i - 1])
 
    # 考虑不偷窃最后一个房屋的情况
    dp2 = [0] * n
    dp2[0] = nums[0]
    dp2[1] = max(nums[0], nums[1])
    for i in range(2, n - 1):
        dp2[i] = max(dp2[i - 2] + nums[i], dp2[i - 1])
 
    return max(dp1[-1], dp2[-2])
# 测试用例1
nums = [2, 3, 2]
print(rob(nums)) # 预期输出为 3
# 测试用例2
nums = [1, 2, 3, 1]
print(rob(nums)) # 预期输出为 4
# 测试用例3
nums = [0]
print(rob(nums)) # 预期输出为 0

3.1.4 算法分析

1.时间复杂度分析：
初始化 dp 数组需要 O(1) 的时间。计算 dp[i] 的过程中，每一步都只涉及常数次的操作，所以计算 dp[i] 的时间复杂度为 O(1)。因此，整个计算 dp 数组的时间复杂度为 O(n)，其中 n 是房屋的数量。

2.空间复杂度分析：

我们需要一个长度为 n 的 dp 数组来存储中间结果，因此空间复杂度为 O(n)。

3.算法正确性分析：

通过使用动态规划的思路，我们将原问题拆分为两个子问题，并分别计算得到最优解。然后，通过比较两个子问题的结果，得到最终的最优解。由于动态规划的递推公式和初始化过程是合理的，因此算法能够正确地计算出今晚能够偷窃到的最高金额。

3.1.5 算法总结

本题同样是我在力扣上选取的动态规划类的算法题。此类题型属于打家劫舍问题，分析是需要注意是否成环的情况。设计的算法通过构建一个 dp 数组来存储在每个位置上偷取房屋时能够获得的最大金额。最终目标是求解 dp 数组的最后一个元素，即考虑偷取所有房屋时能够获得的最大金额。

3.2 股票问题

3.2.1 题目：买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润 。

3.2.2 算法设计思路

本题与实验课上所做的“买卖股票的最佳时机I”不同的是本题股票可以买卖多次了。但需要注意的是由于只有一只股票，所以再次购买前要出售掉之前的股票。根据动态规划的五个步骤，我们可以设计以下算法来计算所能获取的最大利润：

1.确定状态：

在这个问题中，我们可以使用一个二维的dp数组，dp[i][j]表示在第i天结束时，用户手上持有股票的最大收益或者不持有股票的最大收益。其中，i表示天数，j表示是否持有股票（0表示不持有，1表示持有）。

所以，dp数组的含义：

①dp[i][0] 表示第i天持有股票所得现金。

②dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

①第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]

②第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

2.确定递推公式：

对于第i天，可以根据前一天的状态来更新dp数组：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])，表示第i天不持有股票的最大收益，可以选择保持前一天的状态或者卖出手中的股票；

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])，表示第i天持有股票的最大收益，可以选择保持前一天的状态或者买入股票。

3.初始化dp数组：

初始化第0天的状态：

dp[0][0] = 0，表示第0天不持有股票的最大收益；

dp[0][1] = -prices[0]，表示第0天持有股票的最大收益。

1. 确定遍历顺序：

通常是按照天数的顺序进行遍历，从第1天开始更新dp数组。

1. 返回结果

返回dp数组中的最后一个元素dp[n]，其中n为股票价格数组prices的长度。

3.2.3程序实现

def maxProfit(prices):
    # 计算输入列表的长度
    n = len(prices)
    # 如果列表长度小于2，直接返回0
    if n < 2:
        return 0
 
    # 初始化动态规划数组，表示持有股票和不持有股票时的最大收益
    dp = [[0] * 2 for _ in range(n)]
    dp[0][1] = -prices[0]  # 第0天持有股票的最大收益为负的股票价格
 
    # 遍历每一天的价格，更新动态规划数组
    for i in range(1, n):
        # 计算不持有股票时的最大收益
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        # 计算持有股票时的最大收益
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
 
    # 返回最后一天不持有股票时的最大收益
    return dp[n - 1][0]
 
 
# 测试代码
prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

3.2.4 算法分析

1.时间复杂度：

该算法需要遍历股票价格数组一次，对每一天的状态进行更新。因此，时间复杂度为 O(n)，其中 n 为股票价格数组的长度。

2.空间复杂度：

该算法使用了一个二维数组 dp 来存储状态，其大小为 n*2，因此空间复杂度为 O(n)，其中 n 为股票价格数组的长度。

3.正确性分析：通过动态规划的五个步骤，我们可以确定了状态、递推公式、初始化、遍历顺序，并且通过示例进行了推导，证明了算法的正确性。

3.2.5算法总结

该算法利用动态规划的思想，通过记录每一天结束时持有或不持有股票的最大收益，从而计算出最终能获得的最大利润。算法时间复杂度为O(n)，空间复杂度为O(n)。这个算法在只允许买卖一次的情况下已经被广泛运用，而这里我们将其扩展到了多次买卖的情况，通过状态的转移和更新，计算出了最大利润。

第四章：动态规划算法实战之子序列问题

4.1 不连续子序列问题

4.1.1 题目：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

4.1.2 算法设计思路

本题与部分子序列问题的一个很大的区别是不再要求是连续的，但有相对顺序，即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

同样根据动态规划的算法步骤进行本次算法设计。

1. 确定状态，即确定dp数组及其下标的含义

dp[i][j] 表示长度为 [0, i-1] 的字符串 text1 和长度为 [0, j-1] 的字符串 text2 的最长公共子序列的长度。其中，i 和 j 分别表示 text1 和 text2 的下标，范围从 0 到对应字符串的长度减1。

2.确定递推公式

主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

①如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

②如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列和text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

3.初始化边界条件：

首先考虑dp[i][0]的值，由于test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;同理dp[0][j]也是0。

其他下标都是随着递推公式逐步覆盖，初始为多少都可以，我将其统一初始为0。

4.确定遍历顺序：

从左至右遍历 text1 和 text2 的所有字符，依次计算 dp[i][j]。从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：

5.返回结果：

返回 dp[m][n]，其中 m 和 n 分别为 text1 和 text2 的长度。

4.1.3 程序实现

1. def longestCommonSubsequence(text1: str, text2: str) -> int:
2.     m, n = len(text1), len(text2)
3.     dp = [[0] * (n + 1) for _ in range(m + 1)]
5.     for i in range(1, m + 1):
6.         for j in range(1, n + 1):
7.             if text1[i - 1] == text2[j - 1]:
8.                 dp[i][j] = dp[i - 1][j - 1] + 1
9.             else:
10.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
12.     return dp[m][n]
13. text1 = "abcd"
14. text2 = "aecbd"
15. result = longestCommonSubsequence(text1, text2)
16. print(result)  # 输出：3

4.1.4 算法分析与总结

1.时间复杂度：假设 text1 的长度为 m，text2 的长度为 n。填充整个 dp 数组需要遍历 text1 和 text2 的所有字符，因此时间复杂度为 O(m * n)。

2.空间复杂度：使用了一个二维的 dp 数组来保存中间结果，其大小为 (m + 1) * (n + 1)，因此空间复杂度为 O(m * n)。

3.算法正确性分析：

根据定义，dp[i][j] 表示长度为 [0, i-1] 的字符串 text1 和长度为 [0, j-1] 的字符串 text2 的最长公共子序列的长度。

初始化边界条件，当其中一个字符串为空时，最长公共子序列的长度为0，与定义一致。

确定遍历顺序后，通过状态转移方程 dp[i][j] = dp[i-1][j-1] + 1（当 text1[i-1] == text2[j-1]）或 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，不断更新 dp 数组中的值。

最终返回 dp[m][n]，即长度为 m 的字符串 text1 和长度为 n 的字符串 text2 的最长公共子序列的长度。

4.本算法利用动态规划的思想，通过填充一个二维的 dp 数组，计算出两个字符串的最长公共子序列的长度。时间复杂度为 O(m * n)，空间复杂度为 O(m * n)。

4.2 编辑距离问题

4.2.1 题目：编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符、删除一个字符、替换一个字符

4.2.2 算法设计思路

1. 确定dp数组（dp table）以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

1. 确定递推公式

在确定递推公式前，首先考虑编辑的几种操作，如代码所示：

if (word1[i - 1] == word2[j - 1])

    不操作

if (word1[i - 1] != word2[j - 1])

    增/删/换

（1）if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

因为word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。

（2）if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，有以下几种操作：

①操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i - 1][j] + 1;

②操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i][j - 1] + 1;

此处我采用的都是删除操作，没有添加操作，是因为我分析出word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！ dp数组如下图所示意的：

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删元素。

由上面的分析，if (word1[i - 1] == word2[j - 1])时的操作是 dp[i][j] = dp[i - 1][j - 1] 。那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

1. dp数组初始化

由于dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。因此可进行如下情况的初始化：

dp[i][0]是以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。因此dp[i][0]是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;同理dp[0][j] = j;

1. 确定遍历顺序

从如下四个递推公式：

dp[i][j] = dp[i - 1][j - 1]

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

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

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

可以看出dp[i][j]是依赖左方，上方和左上方元素的，所以在dp矩阵中一定是从左到右从上到下去遍历。

1. 返回结果

返回 dp[m][n]，其中 m 和 n 分别为 word1 和 word2 的长度。

4.2.3 程序实现

1. def minDistance(word1: str, word2: str) -> int:
2.     m, n = len(word1), len(word2)
3.     dp = [[0] * (n + 1) for _ in range(m + 1)]
4.     # 初始化dp数组
5.     for i in range(1, m + 1):
6.         dp[i][0] = i
7.     for j in range(1, n + 1):
8.         dp[0][j] = j
9.     # 填充dp数组
10.     for i in range(1, m + 1):
11.         for j in range(1, n + 1):
12.             if word1[i - 1] == word2[j - 1]:
13.                 dp[i][j] = dp[i - 1][j - 1]
14.             else:
15.                 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
16.     # 返回结果
17.     return dp[m][n]

4.2.4 算法分析

1.时间复杂度：假设word1的长度为m，word2的长度为n，填充dp数组的过程需要遍历整个dp数组，即O(mn)。因此，该算法的时间复杂度为O(mn)。

2.空间复杂度：算法中使用了一个二维的dp数组，其大小为(m+1) * (n+1)，因此空间复杂度为O(m*n)。

3.算法正确性分析：该算法采用动态规划的思想，通过填充dp数组来求解最小编辑距离。首先对dp数组进行初始化，然后根据给定的递推公式依次填充dp

数组，最后返回dp[m][n]作为最小编辑距离。算法正确性得到保证。

综上所述，该算法时间复杂度和空间复杂度都为O(m*n)，并且能够正确地计算出将word1转换成word2所需的最少操作数。

4.2.5 算法总结

编辑距离算法是一种动态规划算法，用于计算将一个字符串转换为另一个字符串所需的最少操作数。

通过定义dp数组以及递推公式，可以依次填充dp数组，最终得到最小编辑距离。该算法的时间复杂度和空间复杂度都为O(m*n)，并且能够正确地计算出将word1转换成word2所需的最少操作数。

第五章：实验收获与讨论

​​​​​​​5.1实验收获

1. 通过本次实验，我得到的一个很大的收获便是对动态规划算法有了更深的理解和认识，具体体现在下面三点：

（1）熟悉了动态规划算法的基本思想和解题步骤：将原问题拆解为子问题，找到子问题之间的关系，并通过存储子问题的解来避免重复计算。这种自底向上的递推思路非常有助于解决多阶段决策最优化问题。

（2）掌握了状态定义和状态转移方程的方法：在动态规划中，状态是问题的关键，良好的状态定义可以简化问题，而状态转移方程则是解决问题的核心。通过分析问题的特点，合理定义状态，并找到状态之间的转移关系，可以更好地构建动态规划算法。

（3）加深了对动态规划的时间复杂度分析的认识：动态规划算法通常需要构建一个状态数组来存储中间结果，因此空间复杂度较高。但是，由于动态规划算法的特性，它可以通过存储中间结果来避免重复计算，从而降低时间复杂度。在实际应用中，我们需要权衡空间复杂度和时间复杂度，选择合适的算法。

1. 另一个很大的收获是解题思路方面。最初遇到此类题型并没有一个很清晰的思路，但经过课堂上老师的教学指导和本次动态规划专题实验的训练，我针对此类问题，总结出了自己的思路，其实通俗来讲就是动态规划算法的五大步骤或者说是五大需要思考的关键点，总结如下：

·确定dp数组（dp table）以及下标的含义

·确定递推公式

·dp数组如何初始化

·确定遍历顺序

·举例推导dp数组/返回结果

我认为按照这五个步骤/方面进行算法设计是成功解题的关键，也有助于我们更好的理解动态规划算法！

​​​​​​​5.2实验讨论

1. 关于完全背包问题中遍历顺序的讨论

当解决完全背包问题时，选择遍历顺序的确会对算法的性能产生一定的影响。在具体的完全平方数问题中，我们可以分析一下两种遍历顺序的原理和影响。

（1）外层for遍历背包，内层for遍历物品：

这种遍历顺序的思路是，对于每个正整数 j，我们遍历所有可能的完全平方数 i*i，然后更新 dp[j]。

①优点：可以确保每个和为 j 的完全平方数数量的最小值都得到正确计算，并且不会因为之前的计算结果而产生影响。

②缺点：可能会重复计算相同的子问题，导致算法效率较低。

（2）外层for遍历物品，内层for遍历背包：

这种遍历顺序的思路是，对于每个完全平方数 i*i，我们遍历所有可能的正整数 j，并更新 dp[j]。

①优点：避免了重复计算相同子问题，从而提高了算法的效率。

③缺点：可能会使得某些和为 j 的完全平方数数量的最小值在当前循环中无法得到正确计算，因为它们依赖于之后的完全平方数的计算结果。

综合来看，在这个问题中，两种遍历顺序都是可行的，但需要注意的是在实际编码中需要根据具体情况选择合适的遍历顺序以获得更好的性能。如果重复计算带来的影响不大，可以选择外层for遍历背包，内层for遍历物品；如果算法效率是首要考虑的因素，可以选择外层for遍历物品，内层for遍历背包。

1. 关于动态规划算法与贪心算法异同点的讨论

（以“买卖股票的最佳时机II”为例进行分析讨论）

1. 相同点

①动态规划算法和贪心算法都可以用来解决股票买卖的最佳时机 II 问题。

②它们都具备较低的时间复杂度，可以在合理的时间内得到结果。

1. 不同点

①动态规划算法通过存储中间状态的结果，利用重叠子问题和最优子结构性质，得到最优解，状态转移方程为：dp[i] = max(dp[i-1], dp[i-1] + prices[i] - prices[i-1])，

即当前最大利润等于前一天的最大利润与今天的利润之和的较大值。而贪心算法则通过贪心选择性质，每一步选择当前最优解，最终得到全局最优解。

②动态规划算法需要额外的空间来保存中间状态，而贪心算法只需要维护一个变量即可。

④动态规划算法适用于更一般化的问题，能够处理更复杂的情况。而贪心算法通常适用于某些特定问题，并且对问题的要求较高。

1. 部分动态规划算法可解决的问题，贪心算法无法解决

因为这些问题无法通过贪心策略得到全局最优解。例如，如果问题没有满足贪心选择性质，那么贪心算法可能会产生错误的结果。