动态规划算法,动态规划算法的基本思想
1.斐波那契数列509。斐波那契数
斐波那契数列(通常用F(n)表示)形成的数列称为斐波那契数列。序列从0和1开始，每个后续数字是前两个数字的和。那就是：
F(0)=0，F(1)=1
F(n)=F(n-1) F(n-2)，其中n 1
给定n，请计算F(n)。
示例1:
输入：n=2
解释：F(2)=F(1) F(0)=1 0=1
示例2:
输入：n=3
解释：F(3)=F(2) F(1)=1 1=2
示例3:
输入：n=4
解释：F(4)=F(3) F(2)=2 1=3
0=n=30
解决方案：
类别解决方案：
def fib(self，n: int) - int:
如果n==0:
返回0
如果n==1:
返回1
Dp=[0] * (n 1) #定义Dp数组
Dp[0]=0 #初始化
dp[1]=1
对于范围(2，n ^ 1)中的I:
dp[i]=dp[i-1] dp[i-2] #的递推公式。
返回dp[n]
爬楼梯
70.爬楼梯
假设你正在爬楼梯。你要走n步才能到达屋顶。
一次可以爬1到2级台阶。你有多少种不同的方法可以爬到楼顶？
示例1:
输入：n=2
说明：爬到屋顶有两种方法。
1.一阶一阶
2.二阶
示例2:
输入：n=3
说明：有三种方法可以爬到楼顶。
1.一阶，一阶，一阶
2.一阶和二阶
3.二阶和一阶
1=n=45
爬楼梯本质上也可以看作是一个斐波那契数列：
类别解决方案：
def climbStairs(self，n: int) - int:
DP=[0]*(n ^ 1)
dp[0]=1
dp[1]=1
对于范围(2，n ^ 1)中的I:
dp[i]=dp[i-1] dp[i-2]
返回dp[n]
类似题剑指的是Offer 10- II。青蛙在台阶上跳跃：
类别解决方案：
def numWays(self，n: int) - int:
如果n==0或n==1:
返回1
DP=[0]*(n ^ 1)
Dp[0]=1 # 0步骤有1个方法
Dp[1]=1 # 1一个步骤有一个方法
对于范围(2，n ^ 1)中的I:
dp[i]=dp[i - 1] dp[i - 2]
返回dp[n] % 1000000007
3.不同的道路
62.不同的道路
一个机器人位于一个m x n网格的左上角(起点在下图中标记为“start”)。
机器人一次只能向下或向右移动一步。机器人试图到达网格的右下角(下图中标有“完成”)。
总共有多少条不同的路径？
示例1:
输入：m=3，n=7
产量：28
示例2:
输入：m=3，n=2
从左上角到右下角有3条路径。
1.右下下
2.下-下-右
3.向下-向右-向下
示例3:
输入：m=7，n=3
产量：28
示例4:
输入：m=3，n=3
1=m，n=100
数据保证答案小于等于2 * 109。
问题1:
类别解决方案：
def uniquePaths(self，m: int，n: int) - int:
dp=[[0表示范围(n)中的I]表示范围(m)中的j]
def diff_path(行，列):
#第一列中的任何单元格，仅它上面的单元格中的方法。
对于范围内的I(n):
dp[0][i]=1
#第一行中的任何单元格，只有它前面的单元格的一个方法。
对于范围内的j(m):
dp[j][0]=1
#任何单元格从顶部或左侧都有两条路径。第一行第一列已经填好了，不需要继续填了。
对于范围内的I(1，世界其他地区):
对于范围(1，列)中的j:
dp[i][j]=dp[i - 1][j] dp[i][j - 1]
#返回最后一个单元格的位置
返回dp[row - 1][col - 1]
返回diff_path(m，n)
问题2:(更容易理解)
类别解决方案：
def uniquePaths(self，m: int，n: int) - int:
dp=[[0] * n表示范围(m)中的I]
对于范围中的行(m):
对于范围(n)中的列：
#第一个网格只有一种方法
如果row==0且col==0:
DP[行][列]=1
elif col==0:
#第一行中的任何单元格，只有它前面的单元格的一个方法。
DP[行][列]=DP[行-1][列]
elif row==0:
#第一列中的任何单元格，仅它上面的单元格中的方法。
DP[行][列]=DP[行][列- 1]
否则：
#其他情况(中间):任何单元都有来自其左侧或上方的机器人。
DP[行][列]=DP[行- 1][列]DP[行][列-1]
返回dp[m - 1][n - 1]
4.不同的道路II
63.不同的道路II
示例1:
输入：obstaclegrid=[[0，0，0]，[0，1，0]，[0，0，0]]
说明：在3x3网格的正中央有一个障碍物。
从左上角到右下角有两条不同的路径：
1.右-右-下-下
2.下-下-右-右
示例2:
输入：obstacleGrid=[[0，1]，[0，0]]
m==obstacleGrid.length
n==obstacleGrid[i]。长度
1=m，n=100
Taclegrid [i] [j]是0或1
解决方案：
类别解决方案：
def uniquepathswithdestablishes(self，obstacleGrid:List[List[int]])-int:
row=len(obstacleGrid)
col=len(obstacleGrid[0])
#只有一个单元格时，即一行一列
如果row==1且col==1:
if obstacleGrid[0][0]==1:
返回0
否则：
返回1
dp=[[0] *范围(行)中I的列]
对于范围内的I(世界其他地区):
对于范围内的j(列):
#如果遇到障碍，跳过当前循环
if obstacleGrid[i][j]==1:
继续
如果i==0且j==0:
dp[i][j]=1
elif i==0:
dp[i][j]=dp[i][j - 1]
elif j==0:
dp[i][j]=dp[i - 1][j]
否则：
DP[I]=DP[I][j-1]DP[I-1][j]
返回dp[row - 1][col - 1]
5.最小路径和
64.最小路径和
给定一个包含非负整数的mxn网格，求一条从左上角到右下角的路径，使路径上的数字之和最小。
注意：一次只能向下或向右移动一步。
示例1:
输入：grid=[[1，3，1]，[1，5，1]，[4，2，1]]
说明：因为路径13111的和最小。
示例2:
输入：grid=[[1，2，3]，[4，5，6]]
产量：12
m==网格长度
n==grid[i]。长度
1=m，n=200
0=网格[i][j]=100
解决方案：
类别解决方案：
def minPathSum(self，grid: List[List[int]]) - int:
m，n=len(grid)，len(grid[0])
#只有一个单元格时
如果m==1且n==1:
返回网格[0][0]
dp=[[0] * n表示范围(m)中的I]
对于范围内的I(m):
对于范围(n)中的j:
如果i==0:
#第一行，并且=当前单元格中上一个单元格的编号。
dp[i][j]=dp[i][j - 1]网格[i][j]
elif j==0:
#第一列，并且=当前单元格编号的上一个单元格编号
dp[i][j]=dp[i - 1][j]网格[i][j]
否则：
#中间单元格，并且=前一个单元格和前一个单元格中最小的数字。
dp[i][j]=min(dp[i][j - 1]，dp[i - 1][j])网格[i][j]
返回dp[m-1][n-1]
注意：dp[i][j-1]，dp[i-1][j]代表状态转移，包含了前面路径的总和，而grid[i][j]只代表当前单元格的一个编号，所以是：DP [I] [J]=DP [I] [J-1
6.最长增长子序列
30.最长增长子序列
给你一个整数数组nums，求最长严格递增子序列的长度。
子序列是从数组派生的序列，它删除(或不删除)数组中的元素，而不改变其余元素的顺序。例如，[3，6，2，7]是数组[0，3，1，6，2，2，7]的子序列。
示例1:
输入：nums=[10，9，2，5，3，7，101，18]
说明：最长的递增子序列是[2，3，7，101]，所以长度是4。
示例2:
输入：nums=[0，1，0，3，2，3]
示例3:
输入：nums=[7，7，7，7，7，7]
1=nums.length=2500
-104=nums[i]=104
解决方案：
Dp[i]指示当前元素的增量子集的数量。
元素1:因为没有比它更小的元素，所以增量子集的个数是1。
7:增量子集有：1，17，即1 dp[0]
2:增量子集包括：因为7大于2，所以只有1和12，也就是1 dp[0]
5:增量子集有：1，15，125，即1 dp[2]
以此类推，可以推导出dp[i]。
类别解决方案：
def lengthOfLIS(self，nums: List[int]) - int:
n=len(nums)
如果n==1:
返回1
dp=[1] * n
res=1
对于范围内的I(n):
对于范围(I)中的j:
#将当前元素与其之前的所有元素进行比较。如果前一个元素比当前元素大，跳过它，只考虑比它小的元素。
if nums[i] nums[j]:
dp[i]=max(dp[j] 1，dp[i])
res=max(res，dp[i])
返回资源
参考：[算法太难] [23]最长递增子序列-动态规划
7 .最长公共子序列
143.最长公共子序列
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果没有公共子序列，则返回0。
字符串的子序列是指在不改变字符相对顺序的情况下，从原字符串中删除部分字符(或不删除任何字符)而形成的新字符串。
例如， ace 是 abcde 的子序列，而 aec 不是 abcde 的子序列。
两个字符串的公共子序列是这两个字符串共享的子序列。
示例1:
输入：text1=abcde ，text2=ace
输出：3
说明：最长的公共子序列是“ace ”,长度是3。
示例2:
输入：文本1=abc ，文本2=abc
说明：最长的公共子序列是“abc ”,它的长度是3。
示例3:
输入：文本1=abc ，文本2=def
说明：两个字符串没有公共子序列，返回0。
解决方案：
对于寻找两个字符串的子序列的问题，用两个指针I和J分别在两个字符串上移动，大概率是一种动态规划的思想。
类别解决方案：
def longestCommonSubsequence(self，text1: str，text2: str) - int:
# DP函数的定义：dp(s1，I，s2，j)计算S1[I]的最长公共子序列长度.]和s2[j.]
DP=[[-1 for _ in text 2]for _ in text 1]
定义路径(s1，I，s2，j):
#坏情况，s1或s2此时相当于一个空字符串。
如果len(s1)==i或len(s2)==j:
返回0
#避免重复计算的备忘录
如果dp[i][j]！=-1:
返回dp[i][j]
#比较两个字符串是否相等。如果它们相等，则该字符串必须在lcs中。
如果s1[i]==s2[j]:
dp[i][j]=1路(s1，i 1，s2，j 1)
否则：
#不相等，则s1[i]和s2[j]中至少有一个不在lcs中
dp[i][j]=max(
Ways(s1，i 1，s2，j)，# s1[i]不在lcs中
Ways(s1，I，s2，j 1)，# s2[j]不在lcs中
Ways，i 1，s2，j 1) #不在lcs中(这一步可以省略，因为前两步已经包括在内)
返回dp[i][j]
返回方式(文本1，0，文本2，0)
8.最长回文子序列
56.最长回文子序列
给你一个字符串s，找出最长的回文子序列，返回序列的长度。
子序列被定义为通过删除一些字符或不删除任何字符而不改变剩余字符的顺序而形成的序列。
示例1:
Enter: s=bbbab
解释：一个可能的最长回文子序列是“bbbb”。
示例2:
输入：s=cbbd
解释：一个可能的最长回文子序列是 bb 。
1=长度=1000
s仅由小写英文字母组成。
解决方案：
用dp[i][j]表示字符串S的下标范围[i，j]中最长回文子序列的长度，假设字符串S的长度为n，只有当0=i j n时才会有dp[i][j] 0，否则会有dp[i][j]=0。
类别解决方案：
def longestPalindromeSubseq(self，s: str) - int:
n=透镜
dp=[[0] * n for _ in range(n)]
#逆序递归
对于范围内的I(n-1，-1，-1):
#坏情况，如果只有一个字符，最长回文子序列长度为1，dp[i][j]=1 (i==j)
dp[i][i]=1
对于范围(I ^ 1，n)中的j:
#它们必须在最长的回文子序列中
如果s[i]==s[j]:
dp[i][j]=dp[i 1][j-1] 2
否则：
# s[i 1.j]或s[i.j-1]谁的回文子序列更长？
dp[i][j]=max(dp[i 1][j]，dp[i][j-1])
返回dp[0][n-1]
参考：子序列问题的一般思路最长回文子序列
9.最长的回文子串
5.最长的回文子串
给你一个字符串S，求S中最长的回文子串。
示例1:
Enter: s=babad
输出：“bab”
说明：‘ABA’也是问题的答案。
示例2:
输入：s=cbbd
输出：“bb”
1=长度=1000
s仅由数字和英文字母组成。
解决方案：
解题思路：中心展开法，从当前字符向两端展开(两个指针后移)，在每个位置判断，以那个位置为中心最长的回文串是什么，遍历一遍保留最长的一个。
类别解决方案：
def longest回文(self，s: str) - str:
long_sub=
对于范围内的I(透镜):
Odd=self.is_palindrom(s，I，i) #回文元素个数为奇数。
Even=self.is _ palindrom (s，I，i 1) #回文元素个数为偶数。
long _ sub=odd if len(odd)len(long _ sub)else long _ sub
long _ sub=even if len(even)len(long _ sub)else long _ sub
返回long_sub
def is_palindrom(self，s，l，r):
不超出边界且扩散两边的元素相等，返回回文子串
而l=0和r len(s)和s[l]==s[r]:
l -=1
r=1
返回s[l 1: r]
模拟：
s=babad n=len(s)=5
i=0
奇数：l=0，r=0==s [l]==s [r]==l=-1，r=1==s [0: 1]==long _ sub= b
偶数：l=0，r=1==s[l]！=s[r]===s[0: 1]==long_sub=b
i=1
奇数：l=1，r=1==s [l]==s [r]==l=0，r=2==l=-1，r=3==s [0: 3]==long _ sub= bab
偶数：l=1，r=2==s[l]！=s[r]===s[2: 2]==long_sub=bab
.
参考：[山鬼]左右指针——从中心向外扩散。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。