主要有以下地一些题目：
- 完全平方数
- leetcoad120-三角形最小路径和
- leetcoad62-不同路径
- 不同路径II
- leetcoad343-整数拆分
- leetcoad416-分割等和子集（**这是一个重点地题型，采用了完全背包地思路，并且是一种转换地类型）
- leetcoad198-打家劫舍
- leetcoad213-打家劫舍II
- 子串和子序列地动态规划合集（很经典呀，有很多地类型，关键是里面地一些思路蕴含在里面了）
- 最长公共子序列
- 最长公共子串
- 最长递增子序列
- 最长连续递增序列
- 最长回文子串
- 最长回文子序列
完全平方数
按照找零钱的思路（按照吴师兄的解题步骤：两个题目相互结合起来一起掌握）
- 设置一个数组，用来储存小于n的那些完全平方数
- 用dp[i]表示数字i需要完全平方数的最小数量（最开始初始化为-1，表示还没有计量）
class Solution:
def numSquares(self, n: int) -> int:
# 设置一个数组，用来存储小于 n 的那些完全平方数
square=[]
idx= 1
while idx * idx <=n:
square.append(idx * idx)
idx +=1
# dp[i] 表示数字 i 需要完全平方数的最少数量
# 先让 dp 初始化为 -1，代表 dp[i] 还没有计算，有n+1个初始值，用于储存0~n的所有情况
dp=[-1]*(n+1)
# dp[0] 表示数字 0 需要完全平方数的最少数量
dp[0] = 0
# 开始填充 dp[]
#注意这里i的范围，因为题目给定的n是一个大于等于1的数，所以从1开始遍历
for i in range(1,n+1):
# 在每次填充的过程中，都去遍历 square 数组
for j in range(len(square)):
# 如果发现此时 square 的元素值大于了 i
# 那么 square 后面的那些元素没有必要参与进来计算 i 了
# 直接退出当前的 j 的循环判断，让 i++
if square[j] >i:
break
# 否则，如果 dp[i] 还没有找到数字 i 需要完全平方数的最少数量
# 或者此时计算的新值更小，那么更新 dp[i]
if dp[i]==-1 or dp[i] > dp[i-square[j]]+1:
# 更新 dp[i]
# dp[i] 表示数字 i 需要完全平方数的最少数量
# 这个时候 dp[i] 为获取数字为 square.get(j) 的那 1 个完全平方数
# 加上获取数字为 i-square.get(j) 最少需要 dp[i-square.get(j)] 个数
dp[i]=dp[i-square[j]]+1
# dp[n] 表示数字 n 需要完全平方数的最少数量
# 返回这个结果就行
return dp[n]
尝试采用其他的方式来求解(后面补充进来)：
leetcoad120-三角形最小路径和(middle)
充分的理解题意:寻找每一层数据的条件的限制
按照动态规划的思路来讲这道题并不是很好理解清楚，用下面的图片来进行辅助的理解。，对于第i层来说，第i+1层的数据比这一层要多一个，并且理解当前层的每一个数与i+1层的数的数学关系，确定好数学关系后（如果正位于当前行的下标i，下一步可以移动到下一行的下标i或i+1），就需要再考虑如何进行更新的问题，是一个至底向上的问题
采用递归的方式：既然dp[i][j]只与与该点相邻两点到底边的最小路径和中的较小值有关，结合这道题目采用递归的解法进行相应的尝试,至上而下，存在重复子问题的计算，时间复杂度O(2^n)
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
#本质是一个dfs算法（递归的思路），对每个顶点查找其相邻点的过程
def dfs(i,j,triangle):
# 如果此时的数据正好位于三角形的最底层，没有对应的相邻值，相当于找到递归的出口，直接返回对应的二维数组的值，也就是需要注意的边界问题
if i== len(triangle)-1:
return triangle[i][j]
return triangle[i][j]+min(dfs(i+1,j,triangle),dfs(i+1,j+1,triangle))
# dfs(0,0,triangle)就是要求的最小路径和
return dfs(0,0,triangle)
最后一行换一个位置：
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
return dfs(0,0,triangle)
def dfs(i,j,triangle):
if i== len(triangle)-1:
return triangle[i][j]
return triangle[i][j]+min(dfs(i+1,j,triangle),dfs(i+1,j+1,triangle))
递归+记忆化（至底向上）
定义一个二维数组进行记忆化（以下的两种写法本质上是一样的，只不过一种写的是对原数组进行修改，一种是定义一个dp数组来储存，只不过是以两种方式记录了每次递归的结果）
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle):
# 行至下而上
for i in range(2,n+1):
# 列至右向左
for j in range(i,length+1):
#理解为不断对原list进行修改的一个过程，相较下面的不需要额外的O(n)空间
triangle[length-i][length-j] = triangle[length-i][length-j] +
min(triangle[length-i+1][length-j],triangle[length-i+1][length-j+1])
#最后返回顶部的值
return triangle[0][0]
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# triangle 是个二维数组
# 先获取 triangle 的层数，即一维数组的个数
n = len(triangle)
dp[i][j]表示从点(i,j)到底边的最小路径和
dp=[0]*(n+1)] for _ in range(n+1)]
# 从最后一层开始计算节点的最短路径，直到顶层 0 层为止，索引从n-1~0,其中step=-1，应为0的上一个下一个状态时-1，所以for i in range(n-1,-1,-1),也算一种小的细节方面吧。
for i in range(n-1,-1,-1):
# dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
# 从每一层的第 0 个位置开始，对于第i层的数据来说，有i列数据，本来j的索引从0~i-1,但是因为相邻元素的原因有j+1的情况，为了避免越界的判断，申请i+1列数据，所以range(i+1)
for j in range(i+1):
# dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[i[j]=triangle[i][j] +min(dp[i+1][j],dp[i+1][j+1])
# 返回结果
return dp[0][0]
** 尝试对空间进行优化**
解题步骤：
- 需要先获取三角形的层数
- 创建dp[i]存储的是到i+1层节点的最小路径和，其中前i个位置存储的是到达第i层各个节点的最小路径和（理解二维数组压缩为一维数组的思想：详见注释）
- 通过for循环更新dp数组
# 对二维的动态规划问题进行空间优化
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# triangle 是个二维数组
# 先获取 triangle 的层数，即一维数组的个数
n = len(triangle)
# 设置一个一维数组，动态的更新每一层中当前节点对应的最短路径
# 在上面的代码中，我们虽然定义了NXN的dp数组，但是递归的时候只用到了下一行的dp[i+1][j]和dp[i+1][j+1],因此dp数组不需要定义n行，定义一行就行了，将O(N^2)的复杂度优化为O(N)
# 这里由后面的分析可知，对于存储j的值，因为最底层有一个j+1的缘故，所以数组的长度为n+1
dp=[0 for _ in range(n+1)]
# 从最后一层开始计算节点的最短路径，直到顶层 0 层为止,避免了从顶至底边界判断的问题
for i in range(n-1,-1,-1):
# dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
# 从每一层的第 0 个位置开始
for j in range(i+1):
# dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j]=triangle[i][j] +min(dp[j],dp[j+1])
# 返回结果
return dp[0]
leetcoad62-不同路径(middle)
获取数组的行和列
设置dp[i][j]表示从第0行第0列到达i行j列时不同的路径的数量
同时要注意边界：这里自己再写的时候要注意
# 应该是最好理解和简单的版本了
def uniquePaths(self, m: int, n: int) -> int:
#创建dp数组，并用0进行填充
dp=[[0]*n for _ in range(m)]
# 设置初始条件，从左上角走到左上角的位置
dp[0][0]=1
#当机器人只在第0列移动的时候
for i in range(m):
dp[i][0]=1
#当机器人只在第0行移动的时候
for j in range(n):
dp[0][j]=1
for i in range(1,m):
for j in range(1,n):
#dp[i][j]数组的含义：机器人走到第i行第j列的所有路径之和
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]
上面的代码做一点精简化的处理：
def uniquePaths(self, m: int, n: int) -> int:
#创建dp数组，并用0和1进行填充,其中对于第0行和第0列的数据填1
dp=[ [1]*n] + [ [1] + [0]*(n-1) for _ in range(m)]
dp[0][0]=1
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]
优化为一维动态规划
有空再补充
不同路径II
注意两个特殊的情况，设置两个初始化的情况（一旦发现障碍物就直接退出循环的，不用再往下进行遍历）
其他不是第0行或者是第0列的时候（一旦发现障碍物就退出当前的执行，直接到一个循环中去）
再设置dp数组的时候，观察是否发现障碍物
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# 用0来填充mxn行的二维数组
dp = [[0]*n for _ in range(m)]
# i 从 0 遍历到 m - 1
# 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向下移动一步
# 所以，只能一直向下走，只有这一条路径
for i in range(m):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
# 循环就像跑圈，当你跑到中途时，遇到了break，就退场，再也不跑了。当你跑到中途时，遇到了continue，就返回起点，开始跑下一圈
if obstacleGrid[i][0]==1:
break
# 仅此一条，别无分路
dp[i][0]=1
# j 从 0 遍历到 n - 1
# 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# 由于每次只能向下或者向右移动一步，此时只能向右移动一步
# 所以，只能一直向右走，只有这一条路径
for j in range(0,n):
# 一旦出现了障碍，那么后面所有的位置都是到达不了的，都是默认的 0
if obstacleGrid[0][j]==1:
break
# 仅此一条，别无分路
dp[0][j]=1
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到 n - 1 列
# 填充二维数组 dp 里面的值
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
for i in range(1,m):
for j in range(1,n):
# 由于每次只能向下或者向右移动一步
# 如果此时出现了障碍，那么由于无法到达这个位置，因此不用处理
if obstacleGrid[i][j]==1:
continue
# 位置 (i,j) 的不同路径的数量是由
# 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
# 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
# 两者之和获取到的
dp[i][j]=dp[i-1][j]+dp[i][j-1]
# dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
# 即到达终点的数量
# 返回这个结果即可
return dp[m-1][n-1]
leetcoad343-整数拆分（middle）
dp[i]表示正整数i拆分之后结果的最大乘积
dp[i-j]表示正整数i-j拆分之后结果的最大乘积
对于i有两种拆法：
- j * (i-j) 表示把i拆分为j和i-j这两个数
- j * dp[i - j] 表示把i拆分为j和dp[i-j]这两个数
这个过程其实是需要证明的
j * dp[i - j] >dp[j] * dp[i-j]
dp[j] * dp[i-j]肯定在之前的dp[j-k]*dp[k]*dp[i-j]中已经计算过了
比如拆分10 为4和6
dp[4]dp[6]已经在2dp[8]这种情况中得到了相应的回答了
同样也要注意拆分从你那个3数字开始，dp[2]就是一个边界条件
class Solution:
def integerBreak(self, n: int) -> int:
# dp[2] 表示正整数 2 拆分之后结果的最大乘积
# dp[3] 表示正整数 3 拆分之后结果的最大乘积
# dp[i] 表示正整数 i 拆分之后结果的最大乘积
dp = [ 0 for _ in range( n + 1 )]
# 你可以假设 n 不小于 2 且不大于 58
# 初始化 dp[2]
dp[2] = 1
# 填充数组 dp 里面的值
for i in range( 3 , n + 1 ) :
for j in range ( 1 , i - 1 ):
# 并且，并不是说拆分之后乘积就必然大于 i，比如 i = 2，拆分之后的乘积为 1
# 因此，需要比较这三者，取较大值
dp[i] = max(dp[i], max(j * ( i - j ), j * dp[ i - j ]))
# 返回这个结果即可
return dp[n]
地下城游戏
dp[i][j]表示骑士来到第i行第j列时必须拥有的最小生命值
应该是从右下角开始填充的，从后往前，所以此时的初始状态是反的
leetcoad416-分割等和子集
这道题要十分深刻的掌握！！！（也是今天的死任务，在代码和思维层面都不能有思维的漏洞。）
题目的意思要深刻解析：给你一个只包含整数的非空数组nums，请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
等价转换：是否可以从输入的数组中挑出一些正整数，使得这些数的和等于整个数组元素和的一半。（数组的和一定得是偶数,并且这里的思维转化才是最妙的，如果背包问题没有十分清晰和深刻的认识很难想到用这个方法，也是题目的一大思路点！！！！！！）
与0-1背包的区别：
- 0-1 背包问题选取的物品的容积总量 不能超过 规定的总量；
- 本题选取的数字之和需要 恰好等于 规定的和的一半。
状态转移方程：
状态的定义：
dp[i][j] 表示 nums 的前 i 个元素（从数组[0,i]这个子区间挑选一些整数，每次只能用一次）能否可以组成和为 j 的结果（使得这些数的结果恰好等于j）
状态转移方程：对于0-1背包问题就是考虑当前的数字选与不选的问题
- 不选nums[i]，如果在[0,i-1]的范围内已经有一部分元素，使得他们的和为j，那么dp[i][j]=True
- 如果选择的话，**如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]**。（这里的思路实在是太妙了！！！！！，一下子就找到了思路的源泉，很开心！！！！）dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]]
考虑相应的初始条件
- j-nums[j]作为数组的下标，一定要保证大于等于0，也即j>=nums[i] （也可以从另外的一个角度来理解：只有目标数与当前数的差值大于0才有可能在除开这个数的前面去寻找）
- j恰好等于nums[i]的情况，j==nms[i]（这里是非常特殊的情况：既然容量和给的值正好相等自然是没有问题的）
初始化：dp[0][0]=False：待选的nums[0]是整数，凑不出和为0的情况（这种思维太细了，联想0-1背包问题就是：有物品，但是么有背包容量，此时的背包啥也装不下，这里也是一样的，一个正整数无法凑出一个为0的值。）
下面的这张表是为了让自己有更加深入的了解。
# 以下为python代码的实现过程，仿照了0-1背包的思路
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 将问题转化为为0-1背包问题的形式
# 判读数组的和是否是偶数，如果是奇数就直接pass
temp=sum(nums)
if temp %2==1:
return False
# 构建总的背包容量
target=temp//2
n=len(nums)
# 构建dp数组，其中行数为数组的长度，列数为target+1
# 构建dp数组,默认里面是填充的False,和0-1背包问题默认填0是一个道理
dp=[[False]*(target+1) for _ in range(n)]
#print(dp)
# 设置初始状态,也就是当为nums[0]的时候，由于nums[0]是一个正整数，所以无法凑出0出来。
dp[0][0]=False
# dp[i][j]的含义:在前i个数字中能否找到和为j的数字，如果能的话就是True，如果不能的话就是False
for i in range(n):
for j in range(target+1):
# 想想0-1背包的问题
# 首先判断当前值是否是比j要大的，如果是大的话肯定是不能够凑出来的
# 就需要看前面的数能否凑出j来，也即此时的状态是依赖于上一行的状态
if j<nums[i]:
dp[i][j]=dp[i-1][j]
# 如果当前的值正好是等于j值，这个时候也是可以凑出来的。
elif j==nums[i]:
dp[i][j]=True
# 最后一种情况j>nums[i]
else:
# 这里的情况又要分两种情况
# 选择把把当前元素作为备选的情况，在剩下的元素中找是否有值等于j-nums[i]
# 以及直接不选nums[i],看之前的数里面能否找到，这两种情况只要有一种是可以的就行
dp[i][j]=dp[i-1][j-nums[i]] or dp[i-1][j]
return dp[n-1][target]
leetcoad198-打家劫舍
定义子问题：从k个房间中能够偷到的最大金额
1.方案一：只偷前k-1个房间，最后一间不偷
- 方案二：偷前k-2个房间，再偷最后一间
class Solution:
def rob(self, nums: List[int]) -> int:
# 先获取全部房间的总数
n= len(nums)
if n==1:
return nums[0]
value=[0]*n
value[0]=nums[0]
value[1]=max(nums[0],nums[1])
# value[1] 表示前 1 个房间可以偷取的最大金额
# 只有 1 个房间，那么只能偷这个房间的东西，所以存放结果为这个房间的金额
# 从 i = 2 直到 i = n，value 中存放的结果由前 i - 2 和 i - 1 共同决定
for i in range(2,n):
# 转移方程：value[i] 等于 value[ i - 1 ] 和 value[ i - 2 ] + num[ i - 1] 中的较大值
value[i]=max(value[i-1],value[i-2]+nums[i])
# 最后返回 value 的最后一个值
return value[n-1]
leetcoad213-打家劫舍II
定义子问题：
从k个房间中能够偷到的最大金额（与上一题相同）
1.方案一：只偷前k-1个房间，最后一间不偷（第一家倒数第二家）：nums[1:],有一个最大的金额倒数第一家）：nums[:n-1],有一个最大金额
2. 方案二：偷前k-2个房间，再偷最后一间（第二家
处理房间环的问题：
变化点：房间是一个首位相连的，把一个环的头去掉，就变成打家劫舍的问题（此题的难点和精髓所在）
把环状排列房间问题简化为两个单排列的房间问题，分而治之，把一个问题分成多个规模更小的子问题
房间环状排列 意味着第一间和最后一间不能同时选择，因此我们可以分成两种情况来讨论：（装换成两个打家劫舍的问题，然后再求较大值）
- 不偷窃最后一间房间，那么问题转化为偷窃1号到i - 1号房间所能获得的最高金额。
- 不偷窃第一间房间，那么问题转化为偷窃2号到i号房间所能获得的最高金额。
# 不写函数，直接分类讨论两种情况
class Solution:
def rob(self, nums: List[int]) -> int:
# 先获取全部房间的总数
n = len(nums)
# 初始状态
if n==0:
return 0
if n==1:
return nums[0]
# 方案一：nums[:-1],最后一间不偷的情况
# 1号~i-1号房间所能获得的最高金额
value = [ 0 for _ in range(n+1)]
# 只偷窃1号房间所能获得的最高金额nums[0]
value[1] = nums[0]
# 从2号遍历到n-1号房间
for i in range( 2 , n ) :
value[i] = max(value[i - 1] ,value[i - 2] + nums[i - 1])
# 方案二：nums[:n-1]偷前面的n-2个房间，最后一间可以选择偷或者不偷都行
# 2~i号房间所能获得的最高金额，把第二间房当成单排排列的起点
dp = [ 0 for _ in range(n+1)]
# 只偷窃2号房间所能获得的最高金额
dp[2] = nums[1]
# 从3号遍历到n号房间
for j in range( 3 , n+1) :
dp[j] = max(dp[j - 1] ,dp[j -2] + nums[j - 1])
# 返回值的时候也要注意：需要返回两种请款的较大值，同时要注意下标
return max(value[n-1],dp[n])
# 调用函数进行封装，这种方式从大局到细节都要掌握
class Solution:
def rob(self, nums: List[int]) -> int:
# 先获取全部房间的总数
n = len(nums)
#边界条件
if n == 0 :
return 0
if n == 1 :
return nums[0]
#返回的是只偷前k-1个房间 以及不偷第一家这两种情况的一个最大值
return max(self.myRob(nums[:-1]),self.myRob(nums[1:]))
# 写了一个myRob函数，求这两种情况的一个最大值的问题
def myRob(self, nums: List[int]) -> int:
n = len(nums)
# 多创建了一个数组
value = [ 0 for _ in range( n + 1)]
value[0] = 0
value[1] = nums[0]
# 从 i = 2 直到 i = n，value 中存放的结果由前 i - 2 和 i - 1 共同决定
for i in range( 2 , n + 1 ) :
# 转移方程：value[i] 等于 value[ i - 1 ] 和 value[ i - 2 ] + num[ i - 1] 中的较大值
value[i] = max(value[i - 1] ,value[i - 2] + nums[i - 1])
return value[n]
打家劫舍III(仅学习，是一种树形dp)
关于子串和子序列动态规划合集
这里发现有很多关于子序列与子串的动态规划的问题，这类问题现在这里做一个统一的整理，务必要弄懂和明白，不能有知识的漏洞：
子序列：由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串
回文子串：正读和反读都一样的字符串
回文子序列：它逆序输出和输出之前的序列是一样的
常见的几种类型：
- 求两个数组或两个字符串的最长子序列的问题肯定是需要用动态规划的思想的
- 单个数组或者字符串用一维的dp[i] nums[0:i]中想求的结果
- 当有两个数组或者字符串的时候用到二维的dp[i][j],含义为在A[0:I]和B[0:j]之间匹配想要的结果
- 输出的结果也可能是多样的：
- 输出最长的子序列/子串/回文子序列/回文子串的长度
- 不仅要输出长度，还有输出相应的字符串的具体的值（考验输出的能力的）
以下为几种具体的题目：
- 最长公共子序列
- 最长公共子串
- 最长递增子序列
- 最长连续递增序列
- 最长回文子串
- 最长回文子序列
简要分析（提纲性质的）：
- 其中最长公共子串和最长公共子序列在弄懂概念和区别之后就一定不会弄混的，他们的实现是十分相似的，需要比对清楚。
- 最长递增子序列主要是思想（不一定是连续的或者唯一的）
- 最长连续递增子序列（对最长子序列的一个变式，但是要简单一点，是一个一维的dp问题）
- 最长回文子串和子序列也有相似之处（回文子串只能在原字符串截取，但是回文子序列可以删除原序列的字符来组成）
最长公共子序列
牛客网上做这道题哈还是翻车了，根本没有思路，无法下手
而且在东哥的算法小抄中也是一道重点的题型，经过几次的回顾之后，发现这道题出现的频率还是比较的高，值得自己把它搞懂，搞透，并且要把这一类的问题触类旁通，也是典型的二维dp的问题，并且是两个字符串之间的。遇到子序列的问题就要想到动态规划的思路。子序列的问题用穷举是很难写出来的，动态规划的思想就是穷举+剪枝，是一种很好的匹配的方式。
重点是这里的思路！！！！！！！! ! ! (必须弄懂)
dp[i][j]表示text1前i个字符和text2中前j个字符的最长公共子序列
当前这两个最后的元素是否相同，往前推
实际上是分了三种情况进行考虑的
当最后的一个字符相同的时候：
dp[i-1][j-1]表示text1前i-1个字符和text2中前j-1个字符的最长公共子序列的长度是多少的问题
由于当前两个序列最后的一个元素是相同的，所以dp[i][j]=dp[i-1][j-1]+1
当最后的一个字符不相同的时候：
无法在之前的基础上多得到延申，要么在text1中得到延申，要么在text2中得到延申，现在就是要去找延申哪个字符的问题（为什么要这样想的思路要十分的清晰，这里就有了很明显的动态规划的思想了）
dp[i][j-1]表示text1前i个字符和text2中前j-1个字符的最长公共子序列的长度
：把text1进行延申
dp[i-1][j]表示text1前i-1个字符和text2中前j个字符的最长公共子序列的长度
两者的较大值就是dp[i][j]的值
这里的注意点：需要创建m+1行以及n+1列
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m,n=len(text1),len(text2)
dp=[[0]*(n+1) for _ in range(m+1)]
# print(dp)
# 对text1和text2进行遍历
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][j-1],dp[i-1][j])
return dp[m][n]
leetcoad300-最长递增子序列
这里地关键点是：最长子序列结尾地元素可能是以nums中任意元素结尾(理解的关键点)
同样通过动画自己也是基本已经理解了。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
# 设置一个dp数组，并将其中的值初始化为1
# dp[i]表示以nums[i]结尾的最长递增子序列的长度
dp=[1]*n
# 设置一个数组来记录初始的长度
maxlength=1
# 对dp数组进行遍历
for i in range(n):
# 对原数组进行遍历，其中在遍历的时候不能超过dp中对应的位置
for j in range(i):
# 如果发现nums[i] > nums[j] 并且当前的dp+1要比dp[i]的值要大，说明以最后的一个元素结尾组成的子序列要大一些
if nums[i] >nums[j] and dp[i] <dp[j] +1:
dp[i] = dp[j]+1
# 在每次遍历完内层循环之后(更新dp[i]的过程中)，都需要比较一下此时dp[i]的值与初始化的1哪个更大
if maxlength < dp[i]:
# 把更长的子序列的长度赋予给maxlength
maxlength=dp[i]
return maxlength
leetcoad674-最长连续递增序列（easy）
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
分析：
- 连续递增的子序列，大于它左侧的元素，小于它右侧的元素
- 如果用动态规划的思路的话：dp[i]的含义：以nums[i]结尾的最长连续递增序列的长度
将每一个位置都填充为1（理解） - 要找到最长的，需要定义一个最长的长度
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
# 采用动态规划的思路来解题
# 定义一个变量来定义最长的序列长度，初始值为1，表示只要有元素，最小值肯定是1
maxlengh=1
# dp[i]表示以nums[i]结尾的最长连续递增子序列的长度
n=len(nums)
dp=[1]*n
for i in range(1,n):
# 如果发现后面的数大于前面的数
if i >0 and nums[i]>nums[i-1]:
# 更新dp[i]
dp[i]=dp[i-1]+1
# 每次判断之后就将dp[i]与maxlength进行比较，maxlength只存储最大的值
if dp[i]>maxlengh:
maxlengh=dp[i]
return maxlengh
运用滑动窗口的思想：
https://www.bilibili.com/video/BV1h54y1n7yf?spm_id_from=333.337.search-card.all.click
leetcoad5-最长回文子串
再次回顾这一题的时候希望有不同的感受
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：”bb”
方法一：采用暴力的方法解题
要截取字符串的所有子串，然后再判断这些子串中哪些是回文的，最后返回回文子串中最长的即可
这里我们可以使用两个变量，一个记录最长回文子串开始的位置，一个记录最长回文子串的长度，最后再截取
为了加快访问的速度，我们从最长的字符串开始缩短，这样第一个满足回文子串要求的就是最长的，也即满足题目要求的。
class Solution:
def longestPalindrome(self, s: str) -> str:
n=len(s)
# 从最大的长度开始遍历
for length in range(n,-1,-1):
# 开始位置
for index in range(0,n-length+1):
# 截下来的字符串
sub_string=s[index:length+index]
# 将截下来的字符串倒序
temp=sub_string[::-1]
if sub_string==temp:
# 返回匹配的结果
return sub_string
if __name__=='__main__':
s="cbbd"
res=Solution().longestPalindrome(s)
print(res)
联系最长公共子串的方法
根据回文串的定义：正着读和反着读是一样的，我们可以把原来的字符串倒置，然后找到最长的公共子串就可以了。求最长公共子串的方法有很多，下面也会整理关于最长公共子串的解法。
方法二：采用中心扩散的方法
枚举了所有可能的回文子串的中心的位置
中心位置可能是一个字符，有可能是有两个相邻的字符
记录最长回文子串的相关变量
具体的代码如下：
- 做一个特殊情况的判断
- 枚举回文中心的位置，最后一个位置不需要枚举，不可能再向右边扩散
- 以下标i座作为奇数回文子串的在中心，向两边扩散得到的最长回文子串
- 以下标i作为偶数回文子串的的中心，向两边扩撒得到的最长回文子串
- 左边界向左，有边界向右，直到不能够匹配为止
代码略，后续感兴趣的时候再做更加深入的了解。
方法三采用动态规划的思路
回文串具有天然的状态转移性质的
思路来源：例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。（反过来也是的：一个回文去掉两头之后，剩下的部分依然是回文）
根据这个思路：
在两头字符相等的情况下，整体是否是回文由中间是否是回文来决定
dp[i][j]的含义：字符串s第i个字符和第j个字符之间的子串是否是回文子串（状态转移方程写出来也不容易，还有就是dp数组中存放的是布尔值）
只有[i+1，j-1]是回文子串，并且s的第i个元素和第j个字母相同的时候，s[i:j]才会是回文串
并且在处理的时候，只需要处理i在j左侧的情况，所以也就对应了下面对i和j遍历时候的取值
考虑边界情况：
- 如果数组中只有一个元素，一定是回文子串
- 如果只有两个元素，但是两个元素的值是相同的，那么也是回文子串
最终的答案：
所有dp[i][j]=True中 j-i+1的最大值（从长度较短的字符串向长度较长的字符串进行转移，要注意动态规划的循环顺序）
class Solution:
def getLongestPalindrome(self , A: str) -> int:
# write code here
# 首先回顾回文子串的定义
# 构建dp数组，其中dp[i]表示以当前的元素结尾的回文子串的长度，默认回文子串的长度均为1
# dp[i][j]的含义：**字符串s第i个字符和第j个字符之间的子串是否是回文子串**
n=len(A)
dp=[[False]*n for _ in range(n)]
# 构建判断条件，此元素的对称位置元素相同，这样在这个区间内就构成了一个回文子串
for i in range(n):
dp[i][i]=True
# 记录最长回文子串的长度
max_len=1
# 设置变量记录最长的回文子串的开始位置
# 从后向前寻找
begin=n-1
# 不断地逼近二维数组最右上角地位置，求dp[0][n-1]
for i in range(n-1,-1,-1):
for j in range(i+1,n):
# 如果发现首尾相等
if A[i]==A[j]:
# 如果[i,j]这个区间只有两个字符，并且两个字符还是一样，则必然是回文子串
if (j-i+1)==2:
dp[i][j]=True
# 否则，当前这个区间是否是回文子串取决于[i+1，j-1]是不是回文子串
else:
dp[i][j]=dp[i+1][j-1]
# 如果首尾不相等地话就必然不是回文子串
else:
dp[i][j]=False
# 更新回文子串地长度
if dp[i][j] and j-i+1>max_len:
# 更新最长回文子串地长度
max_len=j-i+1
# 更新最长回文子串开始的位置
begin=i
# 通过截取的方式返回最长回文子串
# return A[begin:begin+max_len]
return max_len
写完动态规划的解法之后，有几点重要的位置仍然需要自己好好的琢磨一下，用云线在图中标识出来了
leetcoad516-最长回文子序列
题目描述：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
理解回文子序列的定义：
子序列：不改变剩余顺序的情况下，删除某些字符或者不删除任何字符形成的序列
子数组：必须连续的
用这张图片来帮助自己去理解
在找到一个回文子序列的基础上继续进行查找，找到一个更长的回文子序列：在已有的回文子序列左右两端加入新的元素组成新的区间，并判断左右两端加入后的长度是否大于之前的回文子序列的长度，如果是就更新最长回文子序列，继续进行查找
- 当左右两边加入的值不相等的时候，需要进行分类讨论
- 只在左边进行加入，能否将之前的回文子序列加长
- 只在右边进行加入，能否将之前的回文子序列加长
- 进行一个对比，把最大的赋值给当前的区间
代码实现：
- dp[i][j]表示字符串s第i个字符和第j个字符之间的最长的回文子序列的长度s[i….j]
- 对于i和j相同的情况，就是单独的一个数，是回文子序列
- j始终在i的右侧
- i从最右边开始，然后往左边移动，j在i的右边，向右边移动（无法直接找到中间两个点然后向两边进行相应的延申）
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# 采用动态规划的思路
# dp[i][j]表示字符串s[i...j]之间的最长回文子序列的长度
# 这里的遍历方式要结合相应的动画来分析：i从后向前遍历，j从i的右边开始从左向右开始遍历
n=len(s)
dp=[[0]*n for _ in range(n)]
for i in range(n):
dp[i][i]=1
for i in range(n-1,-1,-1):
for j in range(i+1,n):
# 当发现s[i]==s[j]的时候，可以让dp[i-1][j-1]上进行相应的扩充，长度+1
if s[i]==s[j]:
dp[i][j]=dp[i+1][j-1]+2
# 当s[i]!=s[j]的时候，这个时候体现了动态规划的思路。将左边的字符串加入和将右边的字符串加入dp[i-][j-1]构成：dp[i][j-1]和dp[i+1][j]
# 比较两者的最大值作为dp[i][j]的值
else:
dp[i][j]=max(dp[i][j-1],dp[i+1][j])
# 循环结束，返回最后的值
return dp[0][n-1]
BM65-最长公共子序列
题目的主要信息：
- 找到两个字符串的最长公共子序列
- 仅存在一个最长的公共子序列，不需要去重
- 没有找到的时候，返回-1，需要变换（这里是一个隐藏的坑）
思路：先得到最长公共子序列的长度（获取长度的思路已经知晓），然后根据这个长度来获取这个子序列（这里才是本道题有一个重点的部分，用到了栈的弹出的小知识，也是一个很关键的点，如果不是做题的话估计自己也很难想到这样的方法。需要对栈进行活学活用，而且要能够快速的反应过来，确实很考验代码和逻辑的思维能力！！！！！！）
在构造表的同时，用一个二维矩阵记录上面状态转移时选择的方向，用1表示来自左上方，用2表示来至左边，用3表示来自上边。
获取这个序列的时候，根据从最后一位开始，根据记录方向，不断地递归往前组装字符，只有来自左上的时候才添加本级字符（这种情况是动态规划中两个字符相等的情况，字符相等的时候才可以用）
这里看得到一个非常好的练习的线上的表格，帮自己完完全全的梳理了一下这个过程，一下子茅塞顿开。
链接如下：https://alchemist-al.com/algorithms/longest-common-subsequence
自己也用excel手动做了一个表格的演示过程
这是一张动态规划的过程图：我用箭头表示的方向就是表的数值不断形成的方向（当遍历的时候最后两个字符不等，来自左边和上边相同的时候，我人为优先来自左边，实际计算机会判断，两个一样大的时候任取一个就行）
下面两张是回溯的过程，目的是为了找到最长的公共子序列到底是哪几个的问题？以下的两种方法都能够找到最长的公共子序列’bcba’,这也是写代码的核心基础部分，这个过程至少是要十分熟悉的。
一开始选择来自上方的情况，就是红色的这个路径：
一开始选择来自左方的情况，就是绿色的这个路径：
class Solution:
def LCS(self , s1: str, s2: str) -> str:
# write code here
# 首先采用二维dp来解题
# dp[i][j]表示s1中前i个字符和s2中前j个字符的最长公公共子序列
# 当两个字符串最后一个字符是相同的时候
# dp[i][j]=dp[i-1][j-1]+1
# 当两个字符串最后一个字符不是相同的时候，看到底是由s1延申过来，还是由s2延申过程
# dp[i][j-1]:表示s1中前i个字符与s2中前j-1个字符的最长公共给子序列
# dp[i-1][j]表示s1中的前i-1个字符与s2中前j个字符的最长公共子序列
m,n=len(s1),len(s2)
dp=[[0]*(n+1) for _ in range(m+1)]
# 初始条件
# 当s1或者s2为空字符串的时候,最长公共子串均为0
if m==0 or n==0:
return '-1'
for i in range(1,m+1):
for j in range(1,n+1):
# 判断当前遍历的最后一个字符是否相
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
# 当最后一个字符不相等的时候
else:
dp[i][j]=max(dp[i][j-1],dp[i-1][j])
# 找到最大长度之后，还要把对应的值给输出来
# return dp[m][n]
#print(dp)
# # 从动态规划数组的末尾开始
i,j=m,n
# 构建一个临时的栈，用来从后向前储存相同的字符
temp=[]
while dp[i][j] !=0:
# 来自左方向
if dp[i][j]==dp[i-1][j]:
i=i-1
# 来自上方向
elif dp[i][j]==dp[i][j-1]:
j= j-1
# 来自左上方
elif dp[i][j]>dp[i-1][j-1]:
i-=1
j-=1
# 只有左上方才是字符相等的情况，入栈，逆序使用
temp.append(s1[i])
# 循环结束之后，进行子序列的拼接
# print(temp)
res=''
while len(temp)!=0:
# 将temp中的元素不断地弹出并加入到res字符串中
res+=temp.pop()
#如果两个完全不同，返回字符串为空，需要改为-1
if res is None or res=='':
return '-1'
else:
return res
BM66- 最长公共子串
注意审题：最长的公共子串，不是最长的公共子序列，子序列可以不是连续的，但是子串一定是连续的。（这里的理解对于做题来说是十分的关键的，一道题能够读懂也十分重要的）
看到题解的时候有一个枚举的思路，对于自己的思维锻炼很有帮助，而且动态规划就是从枚举的思路上发展而来的，需要考验的是自己的能够有枚举的思路，而且还能由枚举来想到用动态规划的思路。（枚举是思维的核心所在！！！！）
参考链接：https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=295&tqId=991150&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
枚举所有的子串进行比较，不用完全枚举的形式，尝试做一点改良
- 遍历两个字符串的所有字符串作为起始(实际上遍历小的就可以了，所以最开始有一个比较大小并互换的过程)
- 同时开始检查字符是否相等，相等的话就不断地后移，增加子串地长度，如果不说明以这两个为起点地子串截至了，不会再有了。(这里也是同动态规划地思想一致的)
- 后续比较长度维护最大值即可。
下面的这种代码的思路上面写的是有点区别的，主要是这行代码：if str1[i - max_len : i + 1] in str2:，可能也是python比较巧妙地一个地方所在。
# 写代码的核心思维思维
class Solution:
def LCS(self , str1: str, str2: str) -> str:
#让str1为较长的字符串
if len(str1) < len(str2):
str1, str2 = str2, str1
res = ''
max_len = 0
#遍历str1的长度
for i in range(len(str1)):
#查找是否存在
if str1[i - max_len : i + 1] in str2:
res = str1[i - max_len : i + 1]
max_len += 1
return res
采用动态规划的思路来解题：
这题和最长的公共子序列也有一定的联系：比如构建dp数组的含义，dp数组的长度以及大小（这种题型要形成自己的思考定式下次碰到的时候就可以直接写了）
定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串，我们首先需要判断这两个字符是否相等。(相当于是递推公式)
- 如果不相等，那么他们就不能构成公共子串，也就是dp[i][j]=0
- 如果相等的话，我们还需要计算前面相等字符的个数：即dp[i-1][j-1]
自己用表格罗列了这样的一个过程，帮助自己去理解。
#很遗憾，采用动态规划的思路，用例并不能全盘的通过
class Solution:
def LCS(self , str1: str, str2: str) -> str:
# write code here
# 设置二维dp数组,dp[i][j]表示在str1的前i个字符，str2的前j个字符中最长公共子串的个数
# 当其中某个字符串长度为0的时候一定是空串
m,n=len(str1),len(str2)
maxlengh=0
dp=[[0]*(n+1) for _ in range(m+1)]
# 分别在两个字符串中进行遍历
# 目的是为了找到最长公共子串的长度
# 其中公共子串是需要连续的
# i在第一个字符串中进行遍历
for i in range(1,m+1):
# j在第二个字符串中进行遍历
for j in range(1,n+1):
# 如果两个字符串当前遍历的最后一个字符相等,就增加公共子串的长度
if str1[i-1]==str2[j-1]:
# 更新，找到它斜上角的值+1
dp[i][j]=dp[i-1][j-1]+1
# 如果不相等的话，需要将dp[i][j]置为0，一旦不等的时候就会断开
else:
dp[i][j]=0
# 判断结束之后，用一个数组来接受最大的长度
if dp[i][j]>maxlengh:
# 更新最大值
maxlengh=dp[i][j]
# 此时pos记录的就是正常字符串的下标（从0开始的）
pos=i-1
# 最后通过对任意一个字符串进行切分来返回最长的公共子串
return str1[pos-maxlengh+1:pos+1]
再次回顾的时候，发现还是做不出来！！！大哭大哭