动态规划 Dynamic Programming 是一种解决多阶段决策过程最优化问题的数学方法它将原问题分解为相对简单的子问题并采用递推的方式求解子问题最终得到原问题的最优解。动态规划算法分为两种类型一种是基于记忆化搜索的自顶向下的方法另一种是基于递推的自底向上的方法。在这两种方法中都需要定义状态和状态转移方程以确定子问题间的递推关系。具体来说我们可以通过以下步骤来设计动态规划算法

确定状态找到问题中的最简单的子问题列出状态表示比如最大子序列问题中状态可能表示为以第i个数为结尾的最大子序列和。

确定状态转移方程列出状态转移方程即当前子问题的最优解如何由前一个子问题的最优解得到。

确定初始状态确定所有子问题中最简单的状态的解通常是边界状态。

确定计算顺序根据状态转移方程确定计算的顺序通常是按照状态的维度进行计算。

优化内存空间如果状态转移只与前一个状态有关则可以不必缓存所有状态只需要缓存前一个状态即可。

简单实例

下面以 LeetCode 509题斐波那契数为例给出一个动态规划算法并加上详细的注解。

题目描述

斐波那契数通常用 F(n) 表示形成的序列称为斐波那契数列。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。即

F(0) 0, F(1) 1 F(n) F(n - 1) F(n - 2), 其中 n 1.

示例 1:

输入: 2 输出: 1 解释: F(2) F(1) F(0) 1 0 1.

示例 2:

输入: 3 输出: 2 解释: F(3) F(2) F(1) 1 1 2.

示例 3:

输入: 4 输出: 3 解释: F(4) F(3) F(2) 2 1 3.

算法实现

确定状态根据题目描述可以定义一个数组 dp[] 来表示斐波那契数列中前n个数字的值 dp[i]表示斐波那契数列中第i个数字的值。

确定状态转移方程根据斐波那契数列的定义 dp[i] dp[i-1] dp[i-2] 其中i 1。

确定初始状态根据斐波那契数列的定义 dp[0] 0 dp[1] 1。

确定计算顺序从左到右依次计算dp[2]、dp[3]、……、dp[n]。

优化内存空间由于状态转移只与前两个状态有关因此可以只用两个变量来记录前两个状态的值不必缓存所有状态。

代码实现

下面是完整的算法实现每一行都有注释说明。

package main
import fmt 
func fib(n int) int {
 if n 2 { // 如果n为0或1 直接返回n
 return n
 dp : [2]int{0, 1} // 定义初始状态 dp[0]表示F(0) dp[1]表示F(1)
 for i : i i { // 从2到n按照状态转移方程求解
 dp_i : dp[0] dp[1] // 计算dp[i] 即F(i)
 dp[0] dp[1] // 更新前两个状态
 dp[1] dp_i
 return dp[1] // 返回最终结果
func main() {
 fmt.Println(fib(2)) // 1
 fmt.Println(fib(3)) // 2
 fmt.Println(fib(4)) // 3

该算法的时间复杂度为 O(n) 空间复杂度为 O(1)。时间复杂度线性空间复杂度常数级别因此在实际应用中较为实用。

进阶实例

下面以 LeetCode 1143题最长公共子序列 LCS 为例运用动态规划两种类型分别实现

题目描述

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

一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。

例如 ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。

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

示例 1

输入 text1 abcde , text2 ace 
输出 3 
解释 最长公共子序列是 ace 它的长度为 3 。

示例 2

输入 text1 abc , text2 abc 
解释 最长公共子序列是 abc 它的长度为 3 。

示例 3

输入 text1 abc , text2 def 
解释 两个字符串没有公共子序列 返回 0 。

提示

1 text1.length, text2.length 1000text1 和 text2 仅由小写英文字符组成。 1. 基于递推的自底向上方法

在该方法中我们从子问题开始依次计算出所有的子问题最终得到原问题的答案。具体地我们使用一个数组来记录子问题的答案然后根据子问题的结果计算更大的问题的答案直到求解出原问题的答案。

例如在求解两个字符串的最长公共子序列问题时我们可以定义一个二维的数组dp[i][j] 表示计算字符串1的前i个字符和字符串2的前j个字符的最长公共子序列。我们首先将数组中所有的元素初始化为0 然后依次遍历字符串1和字符串2的所有字符根据当前字符是否相等来更新数组中的元素

如果第i个字符和第j个字符相同则最长公共子序列长度加1 即dp[i][j] dp[i-1][j-1] 1 如果第i个字符和第j个字符不同则最长公共子序列长度等于前一个状态中两个字符串中较长的那个字符串的最长公共子序列长度即dp[i][j] max(dp[i-1][j], dp[i][j-1])。

最终 dp[m][n]就是字符串1和字符串2的最长公共子序列的长度其中m和n分别为两个字符串的长度。代码如下

package main
import fmt 
func MaxLCS(s1, s2 string) int {
 m, n : len(s1), len(s2)
 dp : make([][]int, m 1)
 for i : range dp {
 dp[i] make([]int, n 1)
 for i : i i {
 for j : j j {
 if s1[i-1] s2[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]
func max(x, y int) int {
 if x y {
 return x
 return y
func main() {
 text1 : abcde 
 text2 : ace 
 fmt.Println(MaxLCS(text1, text2))
 text1 abc 
 text2 abc 
 fmt.Println(MaxLCS(text1, text2))
 text1 abc 
 text2 def 
 fmt.Println(MaxLCS(text1, text2))

2. 基于记忆化搜索的自顶向下方法

在该方法中我们使用递归函数和一个备忘录来实现动态规划。递归函数的基本思想是把原问题划分成若干个子问题每个子问题都解决一次然后将其结果缓存避免重复计算。备忘录记录了已经计算过的子问题的答案如果当前问题之前已经被解决过则直接返回备忘录中的结果。

首先定义了一个 lcs 函数用于递归寻找最长公共子序列。在该函数中我们需要传入两个字符串 s1 和 s2、以及当前的遍历下标 i 和 j 和记忆化数组 memo。memo 用于存储已经遍历过的字符串长度信息避免重复计算公共子序列因为计算公共子序列的递归过程中存在大量的重复计算使用 memo 记录已有的计算结果可以大大提高计算效率。在进行计算前我们首先判断当前查询的两个字符串是否为空如果是则直接返回 0。如果当前条件已经对应 memo 数组中的值则直接返回对应结果。

之后我们通过比较当前遍历的 s1 和 s2 字符串的最后一个字符即 i-1 和 j-1 是否相等分别进行判断。如果相等则将最后一个字符放入公共子序列中长度加 1 递归向前寻找下一个字符如果不相等则通过在 s1 中移去最后一个字符或在 s2 中移去最后一个字符分别计算得到两种情况下的公共子序列并将它们的长度比较大小返回最大的那个长度。

在 MaxLCS 函数中我们定义了一个 memo 数组用于存储已经遍历过的字符串长度信息。在循环初始化 memo 数组时我们将各个位置的值设为 -1 表示尚未进行过计算。最后我们将 s1 和 s2 的两个尾部下标即 len(s1) 和 len(s2) 以及 memo 数组传入 lcs 函数中得到最终的最长公共子序列长度。

代码如下

package main
import fmt 
func lcs(s1, s2 string, i, j int, memo [][]int) int {
 if i 0 || j 0 {
 return 0
 if memo[i][j] ! -1 {
 return memo[i][j]
 if s1[i-1] s2[j-1] {
 memo[i][j] lcs(s1, s2, i-1, j-1, memo) 1
 } else {
 memo[i][j] max(lcs(s1, s2, i-1, j, memo), lcs(s1, s2, i, j-1, memo))
 return memo[i][j]
func MaxLCS(s1, s2 string) int {
 memo : make([][]int, len(s1) 1)
 for i : range memo {
 memo[i] make([]int, len(s2) 1)
 for j : range memo[i] {
 memo[i][j] -1
 return lcs(s1, s2, len(s1), len(s2), memo)
func max(x, y int) int {
 if x y {
 return x
 return y
func main() {
 text1 : abcde 
 text2 : ace 
 fmt.Println(MaxLCS(text1, text2))
 text1 abc 
 text2 abc 
 fmt.Println(MaxLCS(text1, text2))
 text1 abc 
 text2 def 
 fmt.Println(MaxLCS(text1, text2))

本文小结

动态规划是一种通过将原问题拆分成子问题来解决复杂问题的算法。在动态规划中通过记录之前计算的结果可以避免重复的计算从而提高算法效率。

在动态规划问题中通常需要定义状态确定状态转移方程和边界条件。通过状态转移方程可以将问题分解为规模更小的子问题并将子问题的解决结果存储在一个表格中以方便后续的计算。

动态规划常用于解决最长公共子序列、最长递增子序列、背包问题、字符串编辑距离等问题。在解决这些问题时我们需要通过分析问题的特殊性质设计出符合实际情况的状态和状态转移方程。

需要注意的是在设计状态转移方程时需要注意计算顺序尤其是当某个状态的计算依赖于前面的多个状态时需要仔细排列计算顺序避免出现错误的结果。

总之动态规划是一种有效的算法思想可以解决很多实际问题。虽然需要一定的思维难度和技巧但是只要掌握了基本原理和方法就可以灵活地应用到各种场景中解决各种问题。

整理完成后先别急着发表鼠标移动到最下方按钮“保存草稿” 出现“保存并预览”后点击它得到文章链接复制粘贴到CSDN质量分查询页面里查分

https://www.csdn.net/qc

不错果然是好文章可以发表了如果感觉本文有点帮助请收藏点赞写个评论。谢谢

以主题“动态规划法”写一篇博客，以下是我用创作助手InsCode AI辅助写作的全过程，教你分分钟搞定一篇“好”文章！用法简介：1. 以主题线索列举几个提问，比如“何为动态规划法”、“详细介绍一下动态规划算法”、“写一个动态规划算法并做大量注解”。2. 把InsCode AI的答案插入写作文本框，整理之后自拟各段文字的多级标题。3. 最后写段文章小结，插入目录。搞定！正文如下：复制链接

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

更多文章请关注《万象专栏》

转载请注明出处：https://www.wanxiangsucai.com/read/cv182602

话题推荐： #教你# #好文章# #助手# #官方# #CSDN#

打赏
0 赞
收藏
评论
举报

下一篇：四个月内掌握AI快速入门人工智能的关键技能与学习路径

发布评论

全部评论(0)

CSDN官方创作助手InsCode AI 教你分分钟搞定一篇好文章

CSDN官方创作助手InsCode AI 教你分分钟搞定一篇好文章

相关文章