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

🕗 发布于 2024-11-22 03:06 算法 数据结构 动态规划最长公共子串最长回文子串

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]

3. 参考材料

【1】区间 DP：最长回文子序列

原文地址：https://blog.csdn.net/weixin_65514978/article/details/143833419

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：JDBC使用p6spy记录实际执行SQL方法【解决SQL打印两次问题】
下一篇：HarmonyOS4+NEXT星河版入门与项目实战------Button组件

微信小程序数据请求教程：GET与POST请求详解
在微信小程序的开发过程中，数据请求是至关重要的一部分。通过与后端服务器进行通信，小程序能够获取动态数据，实现丰富的功能。在这篇文章中，我们将深入探讨微信小程序中的数据请求，重点介绍GET和POST请求
阅读更多2024-11-26
【Docker系列】批量删除特定前缀的镜像 Tag
💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。非常期待和您一起在这个小小的网络世界里共同
阅读更多2024-11-26
基于Matlab的图像去噪算法仿真（二）
从仿真结果可以看出：邻域平均法实现起来很方便，适用于消除图像中的颗粒噪声，但需要指出这种方法既平滑了图像信号，同时使图像的细节部分变得模糊。如图1-1所示，均值滤波对高斯噪声的抑制是比较好的，但对椒盐
阅读更多2024-11-26
【机器学习】多层神经网络中的误差反向传播算法与过拟合抑制技术的比较与优化
多层神经网络（MLP）是深度学习中的一种基础模型，由多个线性和非线性变换层组成。网络的每一层都由多个神经元组成，每个神经元接收前一层输出的加权和，并通过激活函数进行非线性转换在Python中，我们可以
阅读更多2024-11-26
OpenAI开源Swarm环境搭建&推理测试
该团队还展示了一个应用示例，包括天气查询智能体、用于在航空公司环境中处理不同客户服务请求的多智能体设置、客服机器人、可以帮助销售和退款的个人智能体等。其中，智能体包含指令和工具，并且在任何时间都可以选
阅读更多2024-11-26
2024ARM网络验证支持一键云注入引流弹窗注册机一键脱壳APP加固搭建程序源码及教程
此套源码功能强大，支持APK脱壳、注入、网络验证、注册机、引流弹窗、更新弹窗和公告等功能，并具有强大的系统应用管理端，可轻松管理用户数量和卡密状态等数据统计。armpro脱壳软件可在线修改手机文件和游
阅读更多2024-11-26
[OpenHarmony5.0][Docker][环境]OpenHarmony5.0 Docker编译环境镜像下载以及使用方式
如果你想知道这个镜像是如何制作的，请看下面的教程，如果你只想拿到镜像。那就往下看就好了。
阅读更多2024-11-26
Spring Boot英语知识网站：架构与开发
在整个系统测试中，根据需求文档和设计文档，逐一对功能进行检测并写好测试用例，有效避免残片缺陷，因为产品出现缺陷不仅影响功能，而且可以导致数据的不准确，导致产品质量的降低，经过测试，才能使得产品的稳定性
阅读更多2024-11-26
Java基础设计模式——针对实习面试
本文针对即将实习面试的同学，总结了Java基础中设计模式相关的知识点，希望对大家有所帮助😀
阅读更多2024-11-26
探索运维新视界，CMDB的3D机房功能深度解析
3D 机房是利用三维建模技术，以虚拟的 3D 场景逼真地呈现出机房的物理布局、设备分布以及各种环境信息等。它打破了传统二维平面展示的局限性，将机房中的机柜、服务器、网络设备等以立体的形式展现出来，就如
阅读更多2024-11-26

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

1. 动态规划

2. 问题例子

例子1: 最长公共子序列

1. 状态定义

2. 边界条件

3. 状态转移方程

4. 结果计算

5. 代码

例子2: 最长公共子串

1. 状态定义

2. 边界条件

3. 状态转移方程

4. 结果计算

5. 代码

例子3: 最长回文子序列

1. 状态定义

2. 递推关系

3. 边界条件

4. 最终结果

5. 代码

例子4: 最长回文子串

1. 状态定义

2. 转移方程

3. 初始化

4. 结果计算

5. 代码

3. 参考材料

相关文章