Dynamic Programming

Jessica Gracewell2023-10-042023-10-05

第一部分：简介与基本概念

简介
动态规划（Dynamic Programming，简称DP）是一种在数学和计算机科学中使用的，用于找出多阶段决策过程（经常涉及到时间序列）的最优解的算法设计方法。它通过将复杂问题分解为较简单的子问题来解决问题，通常适用于具有重叠子问题和最优子结构性质的问题。动态规划可用来解决优化问题——这类问题可以有许多可能的解决方案，每一个解都有一个值，我们希望找到具有最优值的解。
什么是动态规划？
动态规划通常用于优化递归问题，例如斐波那契数列。在计算斐波那契数列的一个项时，我们可以先计算其前两项。然而，如果我们用递归的方式，我们将重复计算许多相同的项。动态规划的核心思想是使用变量存储这些计算过的项以便以后使用，从而节省计算时间。这通常称为"记忆化"。
基本特征
动态规划通常适用于具有以下特征的问题：

**最优子结构：**问题的最优解包含其子问题的最优解。
**边界：**问题应该有边界条件来确定解决问题的起点。
**状态转移方程：**解决问题的过程应该能够使用数学方程式进行描述。

第二部分：动态规划的重要性

动态规划的重要性不言而喻。在许多算法问题中，特别是那些涉及到优化问题的，动态规划经常能够提供一种高效的解决方案。与传统的暴力搜索方法相比，它能大大减少不必要的计算，从而在许多情况下显著提高效率。

时间复杂度的降低
通常，通过避免重复计算，动态规划能够将算法的时间复杂度从指数级降低到多项式级。这一点在处理大规模数据或问题时尤为重要。
算法设计的简洁性
动态规划通常能够将问题分解为较小的子问题，这样就可以更简单、更清晰地理解和解决问题。使用动态规划进行算法设计通常能够得到较为简洁和清晰的解决方案。
广泛的应用领域
动态规划在多个领域中都有着广泛的应用，包括但不限于计算机科学、运筹学、工程学等。它可以用来解决诸如路径寻找、资源分配、排程问题等多种问题。
下面我们将通过一个简单的斐波那契数列的实现，来理解动态规划如何在代码中实现。

def fibonacci(n):
    """
    使用动态规划方法计算斐波那契数列的第n项。
    
    参数:
    n (int): 需要计算的斐波那契数列项的位置。
    
    返回:
    int: 斐波那契数列的第n项。
    """
    # 创建一个列表来存储斐波那契数列的值。
    # 为了简化代码，我们将直接计算到第n项，而不是只计算到第n-1项。
    dp = [0] * (n + 1)  # dp[i]将存储斐波那契数列的第i项。
    
    # 初始化斐波那契数列的前两项。
    dp[0] = 0  # 第0项是0。
    dp[1] = 1  # 第1项是1。
    
    # 计算从第2项到第n项的所有斐波那契数值。
    # 我们知道，斐波那契数列的每一项都是其前两项的和，所以我们可以通过循环来计算它。
    for i in range(2, n + 1):
        # 当前项dp[i]等于其前两项dp[i-1]和dp[i-2]的和。
        dp[i] = dp[i-1] + dp[i-2]
        
        # 在这里，我们没有直接递归计算每一项，而是利用前面计算过的项来计算后面的项。
        # 这样我们避免了大量的重复计算，显著提高了算法的效率。
    
    # 返回第n项的值。
    return dp[n]

第三部分：动态规划的核心思想

动态规划的核心思想建立在一个简单的原则上：将大问题分解为小问题，找出各个小问题的解，并利用这些解来构建原问题的解。为了实现这一点，动态规划通常利用了以下几个关键的步骤和概念。

最优子结构
动态规划问题通常展现出所谓的“最优子结构”，即问题的最优解包含其子问题的最优解。在设计动态规划算法时，我们通常需要根据子问题的最优解来构建原问题的最优解。
重叠子问题
动态规划算法通常适用于那些有“重叠子问题”的问题。这意味着在解决问题的过程中，我们会多次遇到同样的子问题。动态规划通过存储这些子问题的解，避免了对同一个问题的重复求解，从而提高了效率。
状态转移方程
“状态转移方程”是描述问题状态如何从一个状态转移到另一个状态的数学方程。在动态规划中，我们需要找到一个状态转移方程，用以表达如何基于子问题的解来得到原问题的解。
存储子问题的解
为了避免重复计算子问题，我们通常使用一个数据结构（如数组或字典）来存储子问题的解。这个数据结构用于在算法执行过程中“记住”已经解决过的子问题的解。

下面，我们将通过一个简单的问题来解释这些概念。问题如下：给定一个整数n，我们希望找到一个方法，来计算n的阶乘（n!）。

我们将使用动态规划的方法来解决这个问题。

def factorial(n):
    """
    使用动态规划方法计算n的阶乘。
    
    参数:
    n (int): 需要计算阶乘的整数。
    
    返回:
    int: n的阶乘。
    """
    # 创建一个列表来存储阶乘的值。
    # dp[i]将存储i的阶乘。
    dp = [0] * (n + 1)
    
    # 初始化阶乘的基础情况。
    # 我们知道，0的阶乘是1。
    dp[0] = 1  
    
    # 计算从1到n的所有阶乘值。
    for i in range(1, n + 1):
        # 当前项dp[i]等于i乘以dp[i-1]。
        # 也就是说，i的阶乘等于i乘以(i-1)的阶乘。
        dp[i] = i * dp[i-1]
        
        # 我们在这里使用了一个循环来计算每一个阶乘值，
        # 而不是使用递归。这样，我们避免了大量的重复计算，
        # 提高了算法的效率。
    
    # 返回n的阶乘。
    return dp[n]

在这个问题中，我们可以看到“最优子结构”和“状态转移方程”的体现。每个阶乘的计算都依赖于前一个数字的阶乘（状态转移），并且构建了问题的最优解（最优子结构）。存储了每个阶乘值的dp数组帮助我们避免了重复计算，实现了动态规划的效率优势。

第四部分：动态规划的基本步骤

动态规划算法通常遵循一系列的基本步骤。理解这些步骤对于构建和优化动态规划算法至关重要。下面，我们将详细讨论这些步骤并提供相关的代码示例。

定义子问题
首先，我们需要将原问题分解为较小的子问题。这通常涉及到将问题分解为较小的、更易管理的部分，这些部分可以单独解决，并且其解可以用来构建原问题的解。
实现要点
**子问题的解决：**我们通常需要找到一个方法来解决每个子问题。
**存储中间状态：**我们通常使用一个数据结构（如数组）来存储子问题的解，以便后续使用。
**构建原问题的解：**一旦我们有了所有必要的子问题的解，我们就需要找到一种方法来利用这些解构建原问题的解。
找出递推关系（状态转移方程）
这一步通常涉及到数学思维。我们需要找到一种方法（通常是一个数学方程），通过这种方法我们可以使用子问题的解来得到原问题的解。
自底向上的计算
最后，我们使用自底向上的方法来解决问题。这意味着我们首先解决最小的子问题，并逐步构建更大的子问题的解，直到我们得到原问题的解。

下面，我们将通过一个例子来展示这些步骤：我们将解决一个简单的问题——计算一个数的阶乘。尽管我们在之前的部分已经解决过这个问题，但我们会在这个部分中更加深入地探讨上述的步骤和概念。

def factorial_detailed(n):
    """
    使用动态规划方法计算n的阶乘，并详细解释每一步。
    
    参数:
    n (int): 需要计算阶乘的整数。
    
    返回:
    int: n的阶乘。
    """
    # 步骤1：定义子问题
    # 我们的子问题是计算每一个小于n的正整数i的阶乘。
    
    # 步骤2：实现要点
    
    # a. 子问题的解决：我们将通过一个循环来解决每个子问题。
    # b. 存储中间状态：我们将使用一个列表dp来存储每个子问题的解。
    #    dp[i]将存储i的阶乘。
    dp = [0] * (n + 1)
    
    # c. 构建原问题的解：我们将通过构建所有必要的子问题的解来构建原问题的解。
    
    # 步骤3：找出递推关系（状态转移方程）
    # 我们知道，i的阶乘是i乘以(i-1)的阶乘。数学上，这可以写作：
    # dp[i] = i * dp[i-1]
    
    # 步骤4：自底向上的计算
    # 我们知道，0的阶乘是1，所以我们从这里开始，并使用我们的状态转移方程来计算所有后续的阶乘值。
    dp[0] = 1  
    for i in range(1, n + 1):
        dp[i] = i * dp[i-1]
    
    # 最后，dp[n]包含n的阶乘。
    return dp[n]

第五部分：案例1 - 斐波那契数列

斐波那契数列是一个经典的展现动态规划思想的例子。这个数列的每一项都是前两项的和，通常定义第0项为0，第1项为1。

我们用自然语言表达数学定义如下：

当 n 等于0时，F(n) 等于0
当 n 等于1时，F(n) 等于1
当 n 大于1时，F(n) 等于 F(n-1) + F(n-2)
虽然我们已在前文中用过这个例子，但现在我们将深入探讨并优化代码实现，添加更多注释以便深入理解。

递归解法
虽然递归解法简单直观，但由于它没有记忆之前的计算结果，当n较大时会造成大量的重复计算，时间复杂度呈指数级增长。
动态规划解法
动态规划解法通过记忆中间状态，避免不必要的计算，将时间复杂度降为线性。让我们通过代码来具体了解这一过程。

def fibonacci_dp(n):
    """
    使用动态规划方法计算斐波那契数列的第n项，并提供详细的注释。
    
    参数:
    n (int): 需要计算的斐波那契数列项的位置。
    
    返回:
    int: 斐波那契数列的第n项。
    """
    # 创建一个列表来存储斐波那契数列的值。
    # dp[i]将存储斐波那契数列的第i项。
    dp = [0] * (n + 1) 
    
    # 我们知道斐波那契数列的前两项是0和1。
    dp[0] = 0  # 第0项是0。
    dp[1] = 1  # 第1项是1。
    
    # 计算从第2项到第n项的所有斐波那契数值。
    for i in range(2, n + 1):
        # 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
        # 这个方程是基于斐波那契数列的定义：每一项都是前两项的和。
        dp[i] = dp[i-1] + dp[i-2]
    
    # 返回第n项的值。
    return dp[n]

第六部分：案例2 - 钢条切割问题

钢条切割问题是一个典型的动态规划问题，它描述了以下场景：我们有一根长度为 n 的钢条，还有一个价格表 P(i)，表示长度为 i的钢条可以卖的价格。我们想要切割钢条并销售，目标是最大化收益。我们可以选择不切割钢条，也可以将钢条切割为任意大小的部分。

朴素递归解法
一个直观的解决方案是使用递归方法，尝试所有可能的切割方案，并选择价格最高的那个。为了找到最优解，我们比较每一种切割方案的收益，并选择收益最高的方案。
动态规划解法
动态规划方法采用更加聪明的方式来解决这个问题。我们将问题分解为更小的子问题，解决这些子问题，并使用这些解决方案来解决原始问题。我们记录下每个子问题的解决方案，确保每个子问题只解决一次，并将结果存储在一个表格中，以便后续使用。

def cut_rod(price, n):
    """
    使用动态规划方法解决钢条切割问题
    
    参数:
    price (list of int): 钢条各长度的价格。
    n (int): 钢条的总长度。
    
    返回:
    int: 切割钢条所能得到的最大收益。
    """
    # 创建一个列表来存储最大收益的值。
    # dp[i]将存储长度为i的钢条的最大收益。
    dp = [0] * (n + 1)  
    
    # 我们要计算长度从1到n的每个钢条的最大收益。
    for i in range(1, n + 1):
        # 初始化长度为i的钢条的最大收益为负无穷大。
        # 这样我们可以确保在后续的比较中，任何正收益都会被认为是更好的方案。
        max_val = float('-inf')
        
        # 我们尝试将钢条切割为两部分：
        # 一部分的长度为j，另一部分的长度为i-j，并且计算两部分的总收益。
        # 我们选择最大的收益作为长度为i的钢条的最大收益。
        for j in range(1, i + 1):
            max_val = max(max_val, price[j-1] + dp[i-j])
        
        # 存储长度为i的钢条的最大收益。
        dp[i] = max_val
    
    # dp[n]现在包含了长度为n的钢条的最大收益。
    return dp[n]

在这个例子中，我们使用了动态规划的思想来优化我们的解决方案。我们将大问题分解为小问题，并使用小问题的解来构建大问题的解。我们避免了重复计算，因为我们存储了中间结果供后续使用。

第七部分：案例3 - 最长公共子序列问题

最长公共子序列问题（Longest Common Subsequence, LCS）也是一个经典的动态规划问题。这个问题是这样定义的：给定两个序列，找到这两个序列共有的、长度最长的子序列。这里的子序列并不要求元素在原序列中是连续的，但要求它们的相对顺序保持不变。

例如，序列"ABCBDAB" 和"BDCAB" 的最长公共子序列是"BCAB"。

朴素解法
我们可以考虑一个简单的递归方法来解决这个问题：我们比较两个序列的每一个元素，并逐步构建最长公共子序列。但是，这种方法涉及大量的重复计算，效率非常低。
动态规划解法
使用动态规划的方法，我们可以存储中间结果，减少不必要的计算。我们可以使用一个二维数组来存储两个序列的每一对元素之间的最长公共子序列的长度。这样，我们就可以利用已知的小问题的解来解决大问题。

def lcs(X, Y):
    """
    使用动态规划方法找到两个字符串的最长公共子序列
    
    参数:
    X, Y (str): 需要找到最长公共子序列的两个字符串。
    
    返回:
    str: 两个字符串的最长公共子序列。
    """
    # 获取两个字符串的长度。
    m = len(X)
    n = len(Y)
    
    # 创建一个二维数组，用于存储中间结果。
    # dp[i][j]将存储X的前i个字符和Y的前j个字符的最长公共子序列的长度。
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 遍历两个字符串的所有字符。
    for i in range(m + 1):
        for j in range(n + 1):
            # 当一个字符串的长度为0时，最长公共子序列的长度为0。
            if i == 0 or j == 0:
                dp[i][j] = 0
            # 当两个字符相等时，
            # 最长公共子序列的长度等于去掉这两个字符后的子串的最长公共子序列的长度加1。
            elif X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            # 当两个字符不等时，
            # 最长公共子序列的长度等于去掉一个字符后的子串的最长公共子序列的长度。
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 重建最长公共子序列。
    i, j = m, n
    lcs_str = []
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs_str.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    # 返回最长公共子序列。
    return ''.join(reversed(lcs_str))

# 测试函数
# 找到两个字符串的最长公共子序列。
X = "ABCBDAB"
Y = "BDCAB"
lcs(X, Y)

第八部分：案例4 - 0-1背包问题

0-1背包问题是动态规划中非常经典的一个问题。问题定义如下：给定一组物品，每种物品都有自己的重量和价值，我们希望在限定的总重量内获取最大的价值。

假设我们有 n 个物品，每个物品的重量为 W(i)、价值为 V(i)。我们的目标是在总重量不超过 W 的情况下，最大化选取物品的总价值。

朴素解法
我们可以尝试所有可能的组合来找到最优解。但是，这种方法的计算复杂度是指数级的，对于较大的问题规模，计算量太大，不是一个实际可行的方法。
动态规划解法
动态规划方法提供了一种更加高效的解决方案。我们可以使用一个二维数组来存储子问题的解，避免重复计算。我们使用一个表格来记录选择前 i个物品、在总重量不超过 j 的情况下的最大价值。

def knapsack(values, weights, W):
    """
    使用动态规划方法解决0-1背包问题
    
    参数:
    values (list of int): 各个物品的价值。
    weights (list of int): 各个物品的重量。
    W (int): 背包的最大承重。
    
    返回:
    int: 在最大承重限制下的物品的最大总价值。
    """
    # 获取物品的数量。
    n = len(values)
    
    # 创建一个二维数组，用于存储中间结果。
    # dp[i][j]将存储前i个物品、在总重量不超过j的情况下的最大总价值。
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # 遍历所有物品和所有可能的总重量。
    for i in range(1, n + 1):
        for w in range(W + 1):
            # 如果当前物品的重量超过了限制，我们不能选择这个物品。
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                # 我们可以选择是否要取这个物品，所以在这两种情况中选择总价值更大的那个。
                # 1. 不取这个物品：dp[i][w] = dp[i-1][w]。
                # 2. 取这个物品：dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1]。
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
    
    # dp[n][W]现在存储了所有物品、在总重量不超过W的情况下的最大总价值。
    return dp[n][W]

# 测试函数
# 各个物品的价值。
values = [60, 100, 120]
# 各个物品的重量。
weights = [10, 20, 30]
# 背包的最大承重。
W = 50

knapsack(values, weights, W)

在这个例子中，我们使用了一个二维数组 dp 来存储中间结果。我们使用了子问题的解来构建原问题的解，并通过避免重复计算来提高算法的效率。

第九部分：案例5 - 最短路径问题

最短路径问题也是一个在实际中应用非常广泛的动态规划问题。问题的定义如下：在图论中，给定一个图（Graph）和一个起始节点，我们希望找到从起始节点到图中所有其他节点的最短路径。

这里我们将着重讨论一种特殊的最短路径问题——Floyd-Warshall算法。这个算法用于找到图中所有节点对之间的最短路径。

问题定义
假设我们有一个图，包含 V 个顶点。我们的目标是找到从每个顶点 v 到所有其他顶点 u 的最短路径。
动态规划解法
Floyd-Warshall算法利用动态规划的思想来解决这个问题。我们使用一个二维数组 dist 来存储节点之间的最短距离。我们逐步更新这个数组，以计算出所有节点对之间的最短距离。

以下是Floyd-Warshall算法的简化版本，我们将在代码中展示其工作原理

def floyd_warshall(graph):
    """
    使用Floyd-Warshall算法计算图中所有节点对之间的最短路径
    
    参数:
    graph (list of list of int): 邻接矩阵表示的图。graph[i][j]是从节点i到节点j的距离。
    
    返回:
    list of list of int: 所有节点对之间的最短路径。
    """
    # 获取图中的节点数量。
    V = len(graph)
    
    # 初始化dist矩阵。dist[i][j]将存储从节点i到节点j的最短距离。
    # 初始时，我们可以将graph矩阵复制到dist矩阵，因为graph[i][j]存储的是从节点i到节点j的直接距离。
    dist = list(map(lambda i : list(map(lambda j : j, i)), graph))
    
    # 遍历所有节点，检查是否节点k在节点i和节点j之间的路径可以作为一个更短的路径。
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 如果通过节点k的路径比当前存储在dist[i][j]中的路径更短，我们更新dist[i][j]。
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # 返回所有节点对之间的最短路径。
    return dist

# 测试函数
# 定义一个图的邻接矩阵。
# graph[i][j]存储的是从节点i到节点j的距离。
# 我们使用float('inf')表示两个节点之间没有直接的边。
graph = [
    [0, 5, float('inf'), 10],
    [float('inf'), 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 1],
    [float('inf'), float('inf'), float('inf'), 0]
]

floyd_warshall(graph)

在这个例子中，我们通过逐步更新 dist 数组来计算图中所有节点对之间的最短路径。我们利用已知的小问题（即较短路径）的解来解决大问题（即较长路径）。

第十部分：案例6 - 矩阵链乘法问题

矩阵链乘法问题是另一个经典的动态规划问题。问题的定义如下：我们有一系列的矩阵，我们希望找到一种乘法顺序，使得执行乘法运算的总代价最小。

假设我们有一系列的矩阵 A1,A2,…,An，我们希望计算这些矩阵的乘积。我们可以通过加括号的方式来改变乘法的顺序，从而改变计算的总代价。我们希望找到一种最优的加括号的方式，使得计算的总代价最小。

问题定义
我们用一个数组
p 来记录矩阵的规模，其中
p[i−1]×p[i] 是矩阵 Ai的规模。

我们希望找到一个最优的加括号的方式，使得计算矩阵链 A1A2…An 的乘积的总代价最小。

动态规划解法
我们可以使用动态规划来解决这个问题。我们使用一个二维数组 m 来存储子问题的解。 m[i][j] 表示计算矩阵链AiAi+1…Aj 的乘积的最小总代价。我们的目标是计算 m[1][n] 的值。

我们可以通过比较所有可能的加括号的方式来找到最优解。我们可以分割矩阵链，将其分为两部分，然后分别计算这两部分的乘积的代价，最后再将这两部分的乘积相乘。

def matrix_chain_order(p):
    """
    使用动态规划方法计算矩阵链乘法的最小总代价
    
    参数:
    p (list of int): 矩阵的规模。p[i-1] x p[i]是矩阵Ai的规模。
    
    返回:
    int: 计算矩阵链乘法的最小总代价。
    """
    # 获取矩阵的数量。
    n = len(p) - 1
    
    # 创建一个二维数组，用于存储中间结果。
    # m[i][j]将存储计算矩阵链Ai...Aj的乘积的最小总代价。
    m = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 当我们只有一个矩阵时，计算代价为0。
    for i in range(1, n + 1):
        m[i][i] = 0
    
    # l是矩阵链的长度。
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = float('inf')
            # 我们尝试所有可能的k值，找到最小的总代价。
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
    
    # m[1][n]现在存储了计算整个矩阵链乘法的最小总代价。
    return m[1][n]

在这个例子中，我们逐步计算了计算不同长度的矩阵链乘法的最小总代价，并存储了这些值，用于计算更大问题的解。我们通过避免重复计算同样的子问题来提高算法的效率。

第十一部分：案例7 - 编辑距离问题

编辑距离问题也是计算机科学中的一个经典问题，它在众多领域，包括自然语言处理、生物信息学等都有着广泛的应用。问题定义如下：给定两个字符串str1和str2，我们希望通过插入、删除、替换操作，将str1转换为str2，并希望找到一种转换方法，使得所需的操作次数最少。

问题定义
我们希望找到一种最优的转换方法，使得将字符串str1转换为字符串str2所需的操作次数最少。
动态规划解法
我们可以使用动态规划来解决这个问题。我们使用一个二维数组 dp 来存储子问题的解。dp[i][j] 表示将字符串str1的前i个字符转换为字符串str2的前j个字符所需的最少操作次数。我们的目标是计算 dp[m][n] 的值，其中m和n分别是str1和str2的长度。

我们可以通过比较str1和str2的字符来找到最优解。我们可以逐个考虑str1和str2的字符，对于每一对字符，我们有几种可能的操作：插入、删除、替换或者不进行操作（如果两个字符相同）。

def edit_distance(str1, str2):
    """
    使用动态规划方法计算两个字符串的编辑距离
    
    参数:
    str1, str2 (str): 需要计算编辑距离的两个字符串。
    
    返回:
    int: 两个字符串的编辑距离。
    """
    # 获取两个字符串的长度。
    m, n = len(str1), len(str2)
    
    # 创建一个二维数组，用于存储中间结果。
    # dp[i][j]将存储将str1的前i个字符转换为str2的前j个字符所需的最少操作次数。
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化dp数组的第一列。
    # 将一个空字符串转换为str2的前j个字符所需的操作次数等于j（插入j个字符）。
    for i in range(m + 1):
        dp[i][0] = i
    
    # 初始化dp数组的第一行。
    # 将str1的前i个字符转换为一个空字符串所需的操作次数等于i（删除i个字符）。
    for j in range(n + 1):
        dp[0][j] = j
    
    # 遍历str1和str2的每个字符，更新dp数组的值。
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # 如果