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

1. 动态规划

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

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

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

2. 问题例子

例子1: 最长公共子序列

  • 两个字符串中,不要求连续但要求相对顺序一致的子序列。
  • 例如:对于字符串 ABCDAEBD,最长公共子序列是 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

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

  1. 只考虑 \text{text}_1[0:i-1]\text{text}_2[0:j]的最长公共子序列;
  2. 只考虑\text{text}_1[0:i]\text{text}_2[0:j-1]的最长公共子序列;
  3. 因此: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] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]

例子2: 最长公共子串

  • 两个字符串中,要求连续且相同的子串。
  • 例如:对于字符串 ABCDAEBD,最长公共子串是 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 = 0end_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] + 1if dp[i][j] > max_length:max_length = dp[i][j]end_pos = ielse: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. 递推关系

  1. 如果两端字符相同(s[i] = s[j]),则最长回文子序列的长度为:

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

    当前回文子序列的两端字符 s[i]s[j]相同,子问题规模缩小为中间部分。

  2. 如果两端字符不同(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] = 1for j in range(i + 1, n):if s[i] == s[j]:dp[i][j] = dp[i + 1][j - 1] + 2else: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. 初始化所有长度为 1 的子串为回文;
  2. 判断长度为 2 的子串;
  3. 按子串长度递增计算更长的子串。

4. 结果计算

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

5. 代码

def longest_palindrome_substring(s):n = len(s)if n < 2:return smax_len = 1begin = 0dp = [[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 - 1if j >= n:breakif s[i] != s[j]:dp[i][j] = False else:if j - i < 3:dp[i][j] = Trueelse:dp[i][j] = dp[i + 1][j - 1]if dp[i][j] and j - i + 1 > max_len:max_len = j - i + 1begin = ireturn s[begin:begin + max_len]

3. 参考材料

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/475483.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

前端两大利器:Vue与TypeScript的渊源

Vue 在前端领域占据着重要地位&#xff0c;是最受欢迎的前端框架之一。它被广泛应用于各种类型的 Web 应用开发&#xff0c;从简单的小型项目&#xff0c;如个人博客、公司宣传网站等&#xff0c;到复杂的大型企业级应用&#xff0c;如电商平台、金融系统等。例如&#xff0c;许…

【Python】使用Windows任务计划程序定时运行Python脚本!

在搭建了一个python 文件以后&#xff0c;如果我们想每天一次或者多次运行这个文件&#xff0c;或者想要一天运行多个python 文件&#xff0c;推荐可以使用&#xff1a; Win的【任务计划程序】 创建【批处理文件&#xff08;.bat&#xff09;】运行Python脚本。 我们可以在Wind…

分布式数据库中间件可以用在哪些场景呢

在数字化转型的浪潮中&#xff0c;企业面临着海量数据的存储、管理和分析挑战。华为云分布式数据库中间件&#xff08;DDM&#xff09;作为一款高效的数据管理解决方案&#xff0c;致力于帮助企业在多个场景中实现数据的高效管理和应用&#xff0c;提升业务效率和用户体验。九河…

Photino:通过.NET Core构建跨平台桌面应用程序,.net国产系统

一、Photino.NET简介&#xff1a; 最近发现了一个不错的框架 Photino.Net 一份代码运行&#xff0c;三个平台 windows max linux &#xff0c;其中windows10,windows11,ubuntu 18.04,ubuntu 20.04 已测试均可以。mac 因为没有相关电脑没有测试。 github:https://github.com/t…

NAT网络地址转换——Easy IP

NAT网络地址转换 Tip&#xff1a; EasylP没有地址池的概念,使用接口地址作为NAT转换的公有地址。EasylP适用于不具备固定公网IP地址的场景:如通过DHCP, PPPOE拨号获取地址的私有网络出口,可以直接使用获取到的动态地址进行转换。 本次实验模拟nat协议配置 AR1配置如下&…

Redis五大基本类型——List列表命令详解(命令用法详解+思维导图详解)

目录 一、List列表类型介绍 二、常见命令 1、LPUSH 2、LPUSHX 3、RPUSH 4、RPUSHX 5、LRANGE 6、LPOP 7、RPOP 8、LREM 9、LSET 10、LINDEX 11、LINSERT 12、LLEN 13、阻塞版本命令 BLPOP BRPOP 三、命令小结 相关内容&#xff1a; Redis五大基本类型——Ha…

单细胞转录组学在植物系统和合成生物学中的应用进展-文献精读83

Advances in the Application of Single-Cell Transcriptomics in Plant Systems and Synthetic Biology 单细胞转录组学在植物系统和合成生物学中的应用进展 最佳实践&#xff1a;教程-文献精读80 摘要 植物是由多种细胞类型组成的复杂系统&#xff0c;其结构呈现出分层的组…

【设计模式】如何用C++实现适配器模式

【设计模式】如何用C实现适配器模式 一、问题背景 用到过很多次适配器模式&#xff0c;一直不理解为什么用这种模式&#xff0c;好像这个模式天生就该如此使用。 实际上&#xff0c;我们很多的理念都源于一些简朴的思想&#xff0c;这些思想不一定高深&#xff0c;但是在保证…

详解八大排序(一)------(插入排序,选择排序,冒泡排序,希尔排序)

文章目录 前言1.插入排序&#xff08;InsertSort&#xff09;1.1 核心思路1.2 实现代码 2.选择排序&#xff08;SelectSort&#xff09;2.1 核心思路2.2 实现代码 3.冒泡排序&#xff08;BubbleSort&#xff09;3.1 核心思路3.2 实现代码 4.希尔排序&#xff08;ShellSort&…

《Django 5 By Example》阅读笔记:p679-p765

《Django 5 By Example》学习第10天&#xff0c;p679-p765总结&#xff0c;总计87页。 一、技术总结 1.channel 书里通过聊天软件功能演示Django中channel以及异步编程的应用&#xff0c;本人对这块不是很熟悉&#xff0c;不做评价。 2.deployment(部署) services:db:imag…

kali搭建pikachu靶场

前言&#xff1a; 总所周知搭个网站需要有apachemysqlphp&#xff0c;Apache是一个开源的Web服务器软件&#xff0c; MySQL是一种关系型数据库管理系统&#xff08;数据库&#xff09;&#xff0c;PHP是一种在服务器上执行的脚本语言 文章内容来自&#xff1a;【黑帽编程与攻…

C++时间复杂度与空间复杂度

一、时间复杂度&#xff08;Time Complexity&#xff09; 1. 概念 时间复杂度是用来衡量算法运行时间随着输入规模增长而增长的量级。它主要关注的是算法执行基本操作的次数与输入规模之间的关系&#xff0c;而非具体的运行时间&#xff08;因为实际运行时间会受硬件、编程语…

【软考】系统架构设计师-信息安全技术基础

信息安全核心知识点 信息安全5要素&#xff1a;机密性、完整性、可用性、可控性、审查性 信息安全范围&#xff1a;设备安全、数据安全、内容安全、行为安全 网络安全 网络安全的隐患体现在&#xff1a;物理安全性、软件安全漏洞、不兼容使用安全漏洞、选择合适的安全哲理 …

SQL Server Management Studio 的JDBC驱动程序和IDEA 连接

一、数据库准备 &#xff08;一&#xff09;启用 TCP/IP 协议 操作入口 首先&#xff0c;我们要找到 SQL Server 配置管理器&#xff0c;操作路径为&#xff1a;通过 “此电脑” 右键选择 “管理”&#xff0c;在弹出的 “计算机管理” 窗口中&#xff0c;找到 “服务和应用程…

类和对象——static 成员,匿名对象(C++)

1.static成员 a&#xff09;⽤static修饰的成员变量&#xff0c;称之为静态成员变量&#xff0c;静态成员变量⼀定要在类外进行初始化。 b&#xff09;静态成员变量为所有类对象所共享&#xff0c;不属于某个具体的对象&#xff0c;不存在对象中&#xff0c;存放在静态区。 …

游戏引擎学习第17天

视频参考:https://www.bilibili.com/video/BV1LPUpYJEXE/ 回顾上一天的内容 1. 整体目标&#xff1a; 处理键盘输入&#xff1a;将键盘输入的处理逻辑从平台特定的代码中分离出来&#xff0c;放入更独立的函数中以便管理。优化消息循环&#xff1a;确保消息循环能够有效处理 …

【JavaEE初阶 — 多线程】线程池

目录 1. 线程池的原理 1.1 为什么要有线程池 1.2 线程池的构造方法 1.3 线程池的核心参数 1.4 TimeUnit 1.5 工作队列的类型 1.6 工厂设计模式 1.6.1 工厂模式概念 1.6.2 使用工厂模式的好处 1.6.3 使用工厂模式的典型案例 1.6.4 Thread…

基于Vue+SpringBoot的求职招聘平台

平台概述 本平台是一个高效、便捷的人才与职位匹配系统&#xff0c;旨在为求职者与招聘者提供一站式服务。平台内设三大核心角色&#xff1a;求职者、招聘者以及超级管理员&#xff0c;每个角色拥有独特的功能模块&#xff0c;确保用户能够轻松完成从信息获取到最终录用的整个…

黑马点评 秒杀下单出现的问题:服务器异常---java.lang.NullPointerException: null(已解决)

前言&#xff1a; 在此之前找了好多资料&#xff0c;查了很多&#xff0c;都没有找到对应解决的方法&#xff0c;虽然知道是userid为空&#xff0c;但不知道要修改哪里&#xff0c;还是自己的debug能力不足&#xff0c;以后得多加练习。。。 问题如下&#xff1a; 点击限时抢…

使用GDB或Delve对已经运行起来的Go程序进行远程调试

同步发布在我的博客&#xff0c;欢迎来点赞。 使用 GDB 或 Delve 对已经运行起来的 Go 程序进行远程调试 使用 GDB 或 Delve 对已经运行起来的 Go 程序进行远程调试 背景 Java 程序可以很方便地通过 jdwp 参数指定一个对外端口进行远程调试&#xff0c;如 java \ -agentlib…