当前位置：首页 > article >正文

【数据结构】用四个例子来理解动态规划算法

article 2024/11/22 8:55:16

1. 动态规划

动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为更小的子问题来求解的算法设计思想，一般用于求解具有最优子结构和重叠子问题性质的问题。动态规划的核心在于：（1）最优子结构--问题的最优解可以由其子问题的最优解构造而来；（2）重叠子问题--在递归求解时，同一子问题会被多次计算。（3）状态转移--通过已解决的子问题计算更大的问题。通过保存已经计算过的子问题的解（通常用数组），可以避免重复计算，从而提高效率。

动态规划一般包括以下几个步骤：

定义状态：用一个数组（或多个数组）表示问题在某个阶段的解。
确定状态转移方程：找到状态之间的递推关系。
初始化：设置基础状态的值（边界条件）。
按顺序计算：根据状态转移方程填充状态表。
返回结果：从状态表中得到问题的解。

2. 问题例子

例子1: 最长公共子序列

两个字符串中，不要求连续但要求相对顺序一致的子序列。
例如：对于字符串 ABCD 和 AEBD，最长公共子序列是 ABD，长度为 3。

1. 状态定义

定义 dp[i][j] 表示 $\text{text}_1[0:i]$ 和 $\text{text}_2[0:j]$ 的最长公共子序列的长度。
其中 $\text{text}_1[0:i]$ 表示字符串 $\text{text}_1$ 的前 i 个字符。

2. 边界条件

当 i = 0 或 j = 0 时，空字符串与任意字符串的最长公共子序列长度为 0。因此： $dp[i][0] = dp[0][j] = 0 \quad \forall \, i, j$

3. 状态转移方程

若当前字符相等（即 $\text{text}_1[i-1] = \text{text}_2[j-1]$ )，则最长公共子序列可以通过将这两个相等字符加入到 $\text{text}_1[0:i-1]$ 和 $\text{text}_2[0:j-1]$ 的最长公共子序列得到，转移公式为：

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

若当前字符不相等，则最长公共子序列的长度取决于以下两种情况的较大值：

只考虑 $\text{text}_1[0:i-1]$ 和 $\text{text}_2[0:j]$ 的最长公共子序列；
只考虑 $\text{text}_1[0:i]$ 和 $\text{text}_2[0:j-1]$ 的最长公共子序列；
因此： $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$

4. 结果计算

$dp[m][n]$ 即为字符串 $\text{text}_1$ 和 $\text{text}_2$ 的最长公共子序列的长度，其中 m 和 n 分别是两个字符串的长度。

5. 代码

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]

例子2: 最长公共子串

两个字符串中，要求连续且相同的子串。
例如：对于字符串 ABCD 和 AEBD，最长公共子串是 B，长度为 1。

1. 状态定义

令 $dp[i][j]$ 表示字符串 $\text{text}_1[0:i-1]$ 和 $\text{text}_2[0:j-1]$ 的以 $\text{text}_1[i-1]$ 和 $\text{text}_2[j-1]$ 结尾的最长公共子串的长度。

2. 边界条件

当 i = 0 或 j = 0 时，空字符串无法形成公共子串，因此： $dp[i][0] = dp[0][j] = 0 \quad \forall \, i, j$

3. 状态转移方程

如果当前字符相等（即 $\text{text}_1[i-1] = \text{text}_2[j-1]$ ），则当前的最长公共子串长度是之前的最长公共子串长度加 1： $dp[i][j] = dp[i-1][j-1] + 1$
如果当前字符不相等，则当前没有公共子串： $dp[i][j] = 0$

4. 结果计算

在整个动态规划表 dp[i][j] 中找到最大值，即为最长公共子串的长度。
如果需要具体的子串，可以通过记录最大值的位置，回溯得到对应的子串。

5. 代码

def longest_common_substring(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0
    end_pos = 0  # 记录子串结束位置

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0

    # 返回最长公共子串及其长度
    return text1[end_pos - max_length:end_pos], max_length

例子3: 最长回文子序列

给定一个字符串 S ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列

1. 状态定义

设 dp[i][j] 表示字符串 s 的下标区间 [i, j] 内的最长回文子序列长度：

dp[i][j] 是子字符串 s[i:j+1] 的最长回文子序列长度。

2. 递推关系

如果两端字符相同（ $s[i] = s[j]$ ），则最长回文子序列的长度为：
$dp[i][j] = dp[i+1][j-1] + 2$
当前回文子序列的两端字符 $s[i]$ 和 $s[j]$ 相同，子问题规模缩小为中间部分。

如果两端字符不同（ $s[i] \neq s[j]$ ），则最长回文子序列为：
$dp[i][j] = \max(dp[i+1][j], dp[i][j-1])$
选择舍弃 $s[i]$ 或 $s[j]$ 其中一个，递归处理子问题。

3. 边界条件

单个字符（长度为 1）自然是回文子序列，长度为 1： $dp[i][i] = 1$

4. 最终结果

最终结果存储在 $dp[0][n-1]$ ，即整个字符串的最长回文子序列长度。

5. 代码

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            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][n - 1]

例子4: 最长回文子串

给定一个字符串 S，找到其中最长的回文子串（要求子串是连续的，且回文即正序和反序相同）。

1. 状态定义

令 $dp[i][j]$ 表示字符串 $S[i:j+1]$ 是否为回文子串：

$dp[i][j] = \text{True}$ ，表示 $S[i:j+1]$ 是回文子串；
$dp[i][j] = \text{False}$ ，表示 $S[i:j+1]$ 不是回文子串。

2. 转移方程

如果 $S[i] = S[j]$ ，那么字符串 $S[i:j+1]$ 是否是回文只取决于内部子串 $S[i+1:j]$ ：

$dp[i][j] = dp[i+1][j-1]$ ，当且仅当 $S[i] = S[j]$

特殊情况：

子串长度为 1 时（即 i = j），所有单个字符都是回文：

$dp[i][i] = \text{True}$

子串长度为 2 时（即 j = i + 1），只要两个字符相等就是回文：

$dp[i][j] = (S[i] = S[j])$

3. 初始化

动态规划的计算顺序是从子串长度短到长。需要：

初始化所有长度为 1 的子串为回文；
判断长度为 2 的子串；
按子串长度递增计算更长的子串。

4. 结果计算

在构造 dp 表的过程中，记录最长回文子串的起始位置和长度。

5. 代码

def longest_palindrome_substring(s):
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 先枚举子串长度
        for L in range(2, n + 1):
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        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
                    begin = i
        return s[begin:begin + max_len]