动态规划引言
关于动态规划的定义，网上有很多，但对于初学者，看了定义之后，多少会有点懵，接下来我打算用俩到三个例题来引入动态规划的定义，我将动态规划分为动态和规划俩部分，动态说明它是变化的，规划说明它是从前到后的，所以综合下来就是后面的由前面或者说受前面影响。
案例分析
1.爬楼梯
题目联接：link
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶
我们仔细分析：
台阶数n：
当n = 4 有5种方法可以爬到楼梯
1阶+1阶+1阶+1阶
1阶+1阶+2阶
1阶+2阶+1阶
2阶+1阶+1阶
2阶+2阶
当n = 5时，有8种方法可以爬到楼梯
1阶+1阶+1阶+1阶+1阶
1阶+1阶+1阶+2阶
1阶+1阶+2阶+1阶
1阶+2阶+1阶+1阶
2阶+1阶+1阶+1阶
2阶+2阶+1阶
2阶+1阶+2阶
1阶+2阶+2阶
我们会发现到达第n阶的方法数等于到达第n-1阶和到达第n-2阶的方法数之和，并且从另一个角度分析，要爬到第n阶楼梯，（由于一次只能跳1级或2级）所以只有从第n-1级台阶或者是第n-2级台阶才能跳到第n级台阶，而第n-1级台阶又只能由n-1级台阶的前俩级台阶跳到，之后也是如此，直到第二级台阶。（关系）
所以当台阶数n>2时，count（n）= count（n-1）+count（n-2）
（count是方法数量）
接下来我们有俩种处理方法：
第一种，首先，我们对第一级和第二级台阶进行初始化，令a = 1表示第一级台阶的方法数，b = 2表示第二台阶的方法数，之后根据他们之间的关系进行求解。
python代码1如下：（自底向上）
a = 1 #第一级台阶方法数
b = 2 #第二级台阶方法数
n = int(input())
i = 3 #我们从第三级台阶开始求解
count = 0 #第n级台阶的方法数
while i<=n:
count = a+b #后一级台阶数等于前俩级台阶数之和
a = b
b = count
i += 1
print(count)
python代码2如下：（自顶向下）
def count(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return count(n-1)+count(n-2)
#主代码
n = int(input())
print(count(n)) #调用函数
俩种写法都可以：但都各有缺点，写法1：当n=1或2时，需要另作处理，写法2：时间复杂度大，为O（2^n），且当n较大时，可能消耗的栈帧可能会导致溢出。
第二种就是动态规划的通用方法：
第一步：先分析，找到关系
第二步：创建一个数组并初始化，就拿爬楼梯来说，当n>2之后，count（n）= count(n-1)+count（n-2），我们可以用一个数组来存储之后求解的值。我们可以创建一个长度为n的数组dp，将dp【0】=1，dp【1】= 2，这样就完成第二步了
第三步：开始求解
我们从下标为2开始求解，直到解完n-1为止，所以存储的dp【n-1】即为我们的解，这里需要提一点：关于dp的创建有俩种，第一种是创建长度为n的dp数组，我们将dp【0】=1，dp【1】= 2，这样初始化，下标0的值就是第一级台阶，下标为1就是第二级台阶，所以第n级台阶的下标是n-1，所以我们求解的结果会存放在dp【n-1】里面
第二种是创建长度为n+1的数组arr，相应地，初始化就要跟着变，arr【0】 = 0，arr【1】= 1，arr【2】 = 2，下标为1表示第一级台阶，下标为2表示第二级台阶，所以第n级台阶下标为n，所以求解结果会存放在arr【n】里面。
python代码如下：
n = int(input())
dp = [0]*n
dp[0] = 1
dp[1] = 2
for i in range(2,n):
dp[i] = dp[i-1]+dp[i-2]
print(dp[n-1])
缺点是当n<=2时，需要另作处理。
2.编辑距离
题目链接: link
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2：
输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
第一步：先分析，我们接下来拿word1 = horse和word2 = ros来讲解，我们可以对字符串进行增、删，替三种操作，并且要保证操作次数最少,并且相同字符的位置可能不同，如horse中的r在第三位，而ros中的r在第一位，所以，种种原因，普通方法很难做出正确的代码，（我试过，但最后得到的并不能保证最少次数），所以这题我会用动态规划来讲解。
先来看一张图，上面一行第一个0表示没有字符，然后我们动态地看，看第二个h，从没有字符到一个字符h，我们需要插入字符h，操作次数加一，再看第三个o，从h到ho我们还需要插入一个字符o，操作次数再加一，后面依旧如此，所以增操作，就等价于dp[i] = dp[i-1]+1,下面一行内的数字，代表变成这样需要的操作次数，如下面一行的5表示从没有字符到horse，需要5次操作。所以我们可以建一个 数组来储存操作次数。
但将俩个字符串放在一起看，需要用二维数组来处理，我们建这样的一个二维数组dp来存储操作次数，然后行和列一起看。
对于dp[1][1]行是r，列是h，对应俩个字符串的第一个字符，我们先判断这俩个字符相不相等，相等,不做处理，进入下一个，对应地，dp[i][j] = dp[i-1][j-1]，如果不相等，就需要进行增，删，替操作，
1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1;
（2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1;
（3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1;
那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有
dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;
需要说明的是增和删操作其实可以互换
python代码如下：文章来源：https://www.toymoban.com/news/detail-848932.html
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# 建二维数组,长度需要加1
dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
#dp = [[0]*(len(word2)+1)]*(len(word1)+1)
#初始化行和列
for i in range(len(word1) + 1):
dp[i][0] = i
for j in range(len(word2) + 1):
dp[0][j] = j
# 从dp[1][1]开始求解
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
if word1[i - 1] == word2[j - 1]: # 由于下标从1，1开始，所以这里是word1[i - 1]
dp[i][j] = dp[i - 1][j - 1]
else:
# 判断最小，因为进行了一次操作，所以后面要加1
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
# return dp[len(word1)][len(word2)] 也可以
return dp[-1][-1]
word1 = 'horse'
word2 = 'ros'
a = Solution()
d = a.minDistance(word1,word2)
print(d)
总结
我们再次看动态规划引言，会有更多的理解，动态规划概念如下：
动态规划把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法–动态规划。
该篇文章旨在帮助理解初学者，让初学者对动态规划有一个大概的理解和认识。可能会有很多地方讲解的不好，还望理解。文章来源地址https://www.toymoban.com/news/detail-848932.html
到了这里，关于【算法入门】浅谈动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
