目录
动态规划
- 基础类题目：斐波那契数列、爬楼梯
- 背包问题
- 打家劫舍，最后一道树形 DP
- 股票问题
- 子序列问题，编辑距离
注意：dp 数组的定义和下标的含义 & 递推公式 & dp 数组如何初始化 & 遍历顺序 & 打印 dp 数组
斐波那契数列-EASY
分析：
斐波那契数列 1 1 2 3 5 8
- 确定 dp 数组的含义：dp[i], 下标 i, 第 i 个斐波那契数的值为 dp[i]
- 确定递推公式：dp[i] = dp[i-1] + dp[i-2]
- dp 数组如何初始化：dp[0] = 1, dp[1] = 1
- 确定遍历顺序：从前向后遍历
- 打印 dp 数组
代码
class Solution:
def fib(self, n: int) -> int:
if n <=1:
return n
dp = [0 for _ in range(n+1)]
dp[0], dp[1] = 0, 1
for i in range(2, n+1, 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
问题：n=45时答案错误
- 当
n的值非常大时，使用列表来存储所有的斐波那契数可能会导致内存使用问题。 - 如果只需要最后一个斐波那契数（即
dp[n]），则不需要存储整个序列。
优化代码
class Solution:
def fib(self, n: int) -> int:
if n <=1:
return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a+b
return b
还是在 n=45 时出错
大整数溢出
可以使用取模运算来避免整数过大，如在计算斐波那契数时使用% 1000000007。
class Solution:
def fib(self, n: int) -> int:
if n <=1:
return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, (a+b) % 1000000007
return b
时间复杂度logn的算法
爬楼梯-EASY
代码
class Solution:
def climbStairs(self, n: int) -> int:
# 定义 dp 数组
dp = [0 for _ in range(n+1)]
# dp[i] 表示 到达第 i 阶有多少种不同的方法
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] =dp[i-1] + dp[i-2]
return dp[n]
思考
为什么爬楼梯不需要防止大整数溢出?
斐波那契数列的一个关键性质是它的项数随着指数增长，但是其值却以非常快的速率增长，很快就会超过大多数编程语言能够表示的整数范围。然而，对于爬楼梯问题，到达第 n 阶楼梯的方法数实际上总是一个正整数，并且这个数总是小于或等于 \(2^{n}\)。这是因为在最坏的情况下，每一步都只走 1 阶，这样就有 \(n\)种 方法；而每一步都走 2 阶，则最多有 \(\frac{n}{2} + \frac{n}{2}\)种方法，这在数值上不会超过 \(2^{n}\)。
使用最小花费爬楼梯-EASY
到达不花费，向上跳才花费。
代码
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
min_cost = math.inf
# 阶梯的层数
n = len(cost)
# dp数组 dp[i]表示到达第i层的最低花费
dp = [math.inf for _ in range(n+2)]
# 顶楼为 n+1
dp[0], dp[1] = 0, 0
for i in range(2, n+1):
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
return dp[n]
不同路径-Middle
代码
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 每次向下或向右一步
# 定义二维 dp 数组
# di[i][j]表示到达(i, j)的不同路径数
dp = [[0 for _ in range(n)] for _ in range(m)]
# 如果 i<m-1, 可以向下走
# 如果 j<n-1，可以向右走
# dp 数组初始化
# 第一行，全为 1
# 第一列，全为 1
for j in range(n):
dp[0][j] = 1
for i in range(m):
dp[i][0] = 1
# 遍历
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[m-1][n-1]
深搜代码 & 超时
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
def dfs(i, j):
if i > m or j > n: # 越界了
return 0
if i == m and j == n: # 找到一种方法
return 1
return dfs(i + 1, j) + dfs(i, j + 1)
return dfs(1, 1)
不同路径II-Middle
代码
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
# 每次向下或者向后，到右下角
# 网格中有障碍物，障碍物网格
# 定义 dp 数组，二维
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
# dp数组初始化
# 障碍物处为 0
# 第一行如果有障碍物，则右侧均为 0
# 第一列如果有障碍物，则下方均为 0
obs_flag = False
for j in range(n):
if obstacleGrid[0][j] == 0 and not obs_flag:
dp[0][j] = 1
if obstacleGrid[0][j] == 1:
obs_flag = True
if obs_flag:
dp[0][j] = 0
obs_flag = False
for i in range(m):
if obstacleGrid[i][0] == 0 and not obs_flag:
dp[i][0] = 1
if obstacleGrid[i][0] == 1:
obs_flag = True
if obs_flag:
dp[i][0] = 0
# 遍历
# 如果当前位置上方有障碍，只能从左侧过来
# 如果当前位置左侧有障碍，只能从右侧过来
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] != 1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = 0
return dp[m-1][n-1]
不同路径 III-HARD
回溯代码 & 四个方向 & 路径数
class Solution:
def uniquePathsIII(self, grid:List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(x:int, y:int, left:int) -> int:
if x<0 or x>=m or y<0 or y>=n or grid[x][y]<0:
return 0 # 不合法
# 到达终点时必须要访问所有的无障碍方格
if grid[x][y] == 2:
return left == 0
# 标记为已访问过
grid[x][y] = -1
# 对当前位置的上下左右四个方向进行递归搜索，并计算路径数。
ans = dfs(x-1, y, left-1) + dfs(x, y-1, left-1) + dfs(x+1, y, left-1) + dfs(x, y+1, left-1)
# 恢复现场
grid[x][y] = 0
return ans
cnt0 = sum(row.count(0) for row in grid)
for i, row in enumerate(grid):
for j, v in enumerate(row):
if v == 1:
return dfs(i, j, cnt0+1)
整数拆分-MID*
代码
class Solution:
def integerBreak(self, n: int) -> int:
# 拆分为 k 个正整数的和，且乘积最大化
# 返回最大乘积
# 定义 dp 数组，dp 数组的含义
# dp[i] 将 i 拆分为 k 个正整数且乘积最大化
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 0
dp[2] = 1
for i in range(3, n+1):
for j in range(1, int(i/2)+1):
dp[i] = max(dp[i], j * dp[i-j], j*(i-j))
print(dp)
return dp[n]
思考
- 对于所求 dp[i]，及要拆分的正整数 i
- 将 i 拆分为 j 和 i-j，此时有两种方案
- i-j 不再拆分
- i-j 再次进行拆分，拆分之后的乘积依赖于dp[i-j]
不同的二叉搜索树-MID
代码
class Solution:
def numTrees(self, n: int) -> int:
# 整数 n
# n 个节点，1-n
# 互不相同的二叉搜索树
# 类似整数拆分
# 11 个节点，左边 5 个，右边 5 个；左边 4 个，右边 6 个；
# n = 0, 0
# n = 1, 1 种
# n = 2, 2 种
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
if n <=1:
return n
dp[2] = 2
for i in range(3, n+1):
for j in range(0, i):
# i个节点，i-1 在子树，拆分为j和i-1-j
dp[i] += dp[j] * dp[i-1-j]
return dp[n]
思考
- 对 i 进行拆分，根节点占用一个值，实际拆分的是 i-1
- 拆分为 j 和 i-1-j，左侧 j 个依赖于dp[j]，右侧 i-1-j 个，依赖于 dp[i-1-j]
- 总的种数为左右两侧相乘
- dp 数组输出化时，dp[0] = 1，0 个节点组成的二叉树不存在，但左侧子树 0 个节点时，算作一种，且需要与右侧种数相乘，故为 1
背包问题-理论基础
01 背包：n 种物品每种物品只有一个。
完全背包：n 种物品每种物品无限个。
多重背包：n 种物品每种物品个数各不相同。
01 背包问题
回溯算法暴力搜索
每个物品两种状态，取 & 不取。
二维 dp 数组解法
dp 数组的含义：[0, i]物品任取放入容量为 j 的背包
递推公式，对于 \(dp[i, j]\) 及物品 i：存在两种状态
- 不放物品 i：依赖于\(dp[i-1, j]\)
- 放物品 i：依赖于 \(dp[i-1, j-w[i]] + v[i]\)
dp数组初始化：行为物品，列为容量
- 第一行初始化，物品 0，如果容量大于物品 0 的容量，最大价值为物品 0 的价值，否则价值为 0.
- 第一列初始化，容量 0，如果物品小于容量 0，则价值为物品的价值，否则价值为 0.
遍历顺序：在这里二维 dp 数组先遍历物品再遍历背包或者先遍历背包再遍历物品都可以。
二维 dp 数组降至一维 dp 数组 & 滚动数组
每一行依赖于上一行的结果，将上一层数据拷贝下来。
dp 数组定义：dp[j] 表示容量为 j 的背包所能装下的最大价值为 dp[j]
递推公式：还是根据物品 i 来考虑的
- 不放物品 i：就是 dp[j]
- 放物品 i：\(dp[j-weight[i]] + value[i]\)
dp 数组的初始化：
- dp[0] = 0
- 非 0 下标时，也要初始化为 0，因为递推公式要对两个价值取最大值，这里应该初始化为一个小的值。
遍历顺序：先遍历物品，再遍历背包，且背包倒序遍历，防止物品重复放入。
面试题目
- 01 背包问题，用二维dp数组实现，两个 for 循环能不能颠倒
- 再用 1 维 dp 数组实现，两个 for 循环可不可以颠倒顺序，容量 for 循环为什么从后向前遍历，二维 dp 数组中为什么不用从后向前遍历
- 1 维 dp 数组是重复利用的
分割等和子集-EASY
一维 dp 数组 代码
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 等分为两部分
if sum(nums) % 2 != 0:
return False
target = sum(nums) // 2
# 定义一维 dp 数组
# 含义：dp[i] 容量为 i 能够容纳的最大价值
dp = [0] * (target+1)
# 初始化，dp[0] = 0，非 0 时也为 0，后续有 max 操作
# 主要这里对物品进行遍历
for num in nums:
# 对从0-target的所有容量进行遍历
for j in range(target, num-1, -1):
dp[j] = max(dp[j], dp[j-num] + num)
return dp[target] == target
思路
- 抽象为 01 背包问题
- 背包容量是从 0 开始的
二维 dp 数组 代码
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2 != 0:
return False
target = sum(nums) // 2
dp = [[False for _ in range(target + 1)] for _ in range(len(nums)+1)]
# 初始化第一列
for i in range(len(nums)+1):
dp[i][0] = True
for i in range(1, len(nums)+1):
for j in range(1, target+1):
if j < nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
return dp[len(nums)][target]
最后一块石头的重量 II-MID
思考
- 回溯暴力应该可以做
- 背包问题
- 两两石头块进行粉碎，求最终的最小值，也可以转化为分成两堆，其和尽量接近，这样相减得到的值最小。
一维 dp 数组代码
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
# 同样分成两堆，要求尽可能接近，这样碰撞的差值最小
target = sum(stones) // 2
# 定义一维 dp 数组
dp = [0] * (target+1)
# 含义 容量为 0 的背包，能装的最大价值
# 初始化
# 遍历顺序
for i in range(len(stones)):
# 内层循环保证了容量 j 都比 stone[i]要大
for j in range(target, stones[i]-1, -1):
dp[j] = max(dp[j], stones[i] + dp[j - stones[i]])
return sum(stones) - dp[target]*2
目标和-MID *
思路
- 对于每一个元素，要么加要么减，类似于要么选，要么不选，所以回溯暴力算法应该可以解。
- 加和减也可以看做两个集合，（分割等和子集是两个集合相等，最后一块石头的重量是两个集合尽可能接近），这道题要求两个集合的总和为指定的 target。
- 给定的 nums 为非负整数数组，可以拆分为两个集合，两个集合相减最终得到的值为 target。
如果一个集合，被减数为 A
\(A - (sum-A) = target, A-sum + A = target\)
\(A = \frac{sum + target}{2}\)
故 \(sum + target\)一定能够整除 2.
dp 数组含义：dp[j] 表示容量为 j 的背包得到价值为 add 有 dp[j]种方法，总的方法为 dp[0] + dp[1] + … + dp[j]
问题就是在集合nums中找出和为 add 的组合。
确定递推公式
- 要求 dp[j]，如果加入 nums[i]，则取决于dp[j - nums[i]]
- 类似的组合问题
dp[j] += dp[j - nums[i]]
一维 dp 数组代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 题目拆解：运算结果等于 target == 背包容量为 target 时，容纳的最大价值为 target
# 每个元素两种状态，加或减
# 加集合，减集合
# 要求加集合 - 减集合 = target
# 问题抽象：加集合，背包问题，容量为加集合的背包所能容纳的物品价值恰好等于容量，且减去减集合后为 target
# 加集合 = add
if sum(nums) < abs(target):
return 0
add = (sum(nums) + target) // 2
if (sum(nums) + target) % 2 != 0:
return 0
# 定义 dp 数组
dp = [0] * (add + 1)
# dp数组初始化
# 背包容量为 0，装满背包有 1 中方法
dp[0] = 1
# 考虑物品 num
for num in nums:
for j in range(add, num-1, -1):
dp[j] += dp[j-num]
return dp[add]
二维 dp 数组代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total_sum = sum(nums)
if total_sum < abs(target):
return 0
if (target + total_sum) % 2 != 0:
return 0
# 目标和
target_sum = (target + total_sum) // 2
#创建二维 dp 数组，行表示选取的元素数量，列表示累加和
dp = [[ 0 for _ in range(target_sum + 1)] for _ in range(len(nums)+1)]
# 初始化：0 个物品装满容量为 0的背包，方法有一种
dp[0][0] = 1
# 遍历
for i in range(1, len(nums)+1):
# 容量从 0-target_sum
for j in range(target_sum+1):
# 不选取当前物品
dp[i][j] = dp[i-1][j]
if j >= nums[i-1]:
# 选当前物品
dp[i][j] += dp[i-1][j - nums[i-1]]
return dp[len(nums)][target_sum]
- 当前元素为 \(nums[i]\)，上一个元素为 \(nums[i-1]\)
- 不选取当前物品时 ✅
- 选取当前物品：如果当前容量为 j，要考虑当前容量是否大于上一个元素 \(nums[i-1]\)，如果大于则 \(dp[i][j]\) 可以依赖于 \(dp[i-1][j-nums[j-1]]\)
- +=
一和零-MID*
子集需要满足：最多 m 个 0 ，最多 n 个 1
求：这样的子集最多有多少个元素
思路
m个 0，n 个 1 的容器，装满这个容器，最多有多少个元素。
容器==背包，两个维度的背包，之前的背包只有一个容量的维度，现在相当于是一个容量装 0，一个容量装 1，两个维度。
装满这个背包最多有多少个物品。
零一背包，每个物品只能使用一次。
3 个变量，m，n，最多多少个物品。
每个物品的重量其实就是每个字符串包含 x 个 0 和 y 个 1.
定义二维 dp 数组
\(dp[i][j]\) 定义为 m=i，n=j 的背包最多装多少个物品。
递推公式
当前物品的重量：x 个 0，y 个 1
选中当前物品之后，数量要+1
\(当前物品 重量(Num_0, Num_1) = (x, y)\)
\(dp[i-x][j-j] + 1\)
二维 dp 数组代码
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
# 二进制字符串数组
# 最大子集长度
# 最大子集最多包含 m 个 0，n 个 1
# 该子集看做一个背包，两个维度的背包 m 和 n
# 定义二维 dp 数组
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
# 含义 dp[i][j]
# m = i,n = j 的背包，最多装的物品数为 dp[i][j]
# 初始化
dp[0][0] = 0
# 物品个数
num = len(strs)
# 0维度重量
weight_0 = [0] * num
weight_1 = [0] * num
for idx, ss in enumerate(strs):
for ch in ss:
if ch=='1':
weight_1[idx] += 1
else:
weight_0[idx] += 1
# print(weight_0)
# print(weight_1)
# 初始化
# 非 0 索引肯定初始化为 0 没问题，要取 max 操作
# 第一行 & 第一列 是否需要额外处理
# 遍历顺序
# 遍历物品
for idx in range(num):
# 遍历背包 背包是二维的
# 容量和物品重量的关系在 range 中进行限制
for i in range(m, weight_0[idx]-1, -1):
for j in range(n, weight_1[idx]-1, -1):
dp[i][j] = max(dp[i][j], dp[i-weight_0[idx]][j-weight_1[idx]]+1)
return dp[m][n]
53-最大子数组和-中等
动态规划
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
'''
最大和，连续子数组
动态规划
'''
arr = nums.copy()
for i in range(1, len(arr)):
arr[i] = max(arr[i], arr[i-1]+arr[i])
return max(arr)
918-环形子数组的最大和-中等
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
'''
环形数组
最大子数组的两种情况：
1. 包含首尾：中间即为最小子数组，求最小子数组和
2. 不包含首尾
维护最大前缀和 & 最小前缀和
'''
n = len(nums)
max_ = float('-inf')
min_ = float('inf')
# 无环
pre = 0 # 以nums[i]结尾的最大前缀和
for i in range(n):
if pre > 0:
pre = pre + nums[i]
else:
pre = nums[i]
max_ = max(max_, pre)
# 如果最大子数组和小于0，说明数组全是负数，返回最大的负数即可
if max_<0:
return max(nums)
# 有环
pre = 0 # 以nums[i]结尾的最小前缀和
for i in range(n):
if pre > 0:
pre = nums[i]
else:
pre = pre + nums[i]
min_ = min(min_, pre)
return max(max_, sum(nums)-min_)
一维动态规划
70-爬楼梯-简单
看示例，我们当前应该是处于第0阶
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1] * (n+1)
for i in range(2, n+1):
dp[i] = dp[i-1]+ dp[i-2]
return dp[n]
198-打家劫舍-中等-记住
class Solution:
def rob(self, nums: List[int]) -> int:
'''
相邻的不能偷
'''
n = len(nums)
dp = [0] * (n+1)
# dp[i]表示偷窃前i个房子满足条件获得的最大值
# dp[i]考虑当前nums[i-1]偷还是不偷
dp[0] = 0
dp[1] = nums[0]
for i in range(2, n+1):
dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
return dp[n]
空间优化
class Solution:
def rob(self, nums: List[int]) -> int:
'''
很多时候我们并不需要始终持有全部的 DP 数组
对于小偷问题，我们发现，最后一步计算 f(n) 的时候，实际上只用到了 f(n−1) 和 f(n−2) 的结果
只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题
'''
prev = 0
curr = 0
for i in nums:
# 循环开始时，curr表示dp[i-1]，prev表示dp[i-2]
prev, curr = curr, max(curr, prev+i)
# 循环结束时，curr表示dp[i]，prev表示dp[i-1]
return curr
139-单词拆分-中等
动态规划
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
'''
回溯算法超时
动态规划，表示字符串s的前i个字母是否能够被表示
'''
n = len(s)
dp = [False] * (n+1)
dp[0] = True
for i in range(n): # 起点
for j in range(i+1, n+1):
if dp[i] and s[i:j] in wordDict:
dp[j] = True
return dp[-1]
记忆化回溯
对剩余字符串进行递归调用，将剩余字符串的调用结果进行缓存
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
'''
记忆化回溯
使用装饰器，装饰器可以保存函数的执行结果，缓存
'''
import functools
# 使用lru_cache装饰器来缓存back_track函数的结果，None参数表示缓存所有调用的结果，有助于避免重复计算
@functools.lru_cache(None)
def back_track(s: str):
# s为剩余需要匹配的字符串
if not s:
return True
res = False
for i in range(1, len(s)+1):
if s[:i] in wordDict:
res = back_track(s[i:]) or res
return res
return back_track(s)
322-零钱兑换-中等
动态规划
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
'''
不同面额的硬币
总金额
凑成总金额所需的最少金币数
'''
dp = [math.inf] * (amount+1)
dp[0] = 0
for i in coins:
if i<=amount:
dp[i] = 1
for i in range(1, amount+1):
if dp[i] != math.inf:
continue
for j in coins:
if i-j >=1:
dp[i] = min(dp[i], dp[i-j]+1)
else:
continue
if dp[-1] == math.inf:
return -1
return dp[-1]
完全背包问题
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = amount
dp = [math.inf] * (n+1)
dp[0] = 0
# 遍历物品
for coin in coins:
# 遍历背包
for i in range(coin, n+1):
dp[i] = min(dp[i], dp[i-coin]+1)
if dp[-1] == math.inf:
return -1
return dp[-1]
300-最长递增子序列-中等
动态规划
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
'''
最长增长子序列
整数数组，严格递增 子序列 相对顺序不改变
'''
n = len(nums)
dp = [1] * n
# dp[i] 表示到i为止最长的递增子序列
for i in range(n):
for j in range(i, -1, -1):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
多维动态规划
120-三角形最小路径和
动态规划，填充主对角线左侧三角区域
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
'''
只能移动到下一行的相邻结点
二维dp数组
'''
n = len(triangle)
dp = [[math.inf for _ in range(n)] for _ in range(n)]
dp[0][0] = triangle[0][0]
# 从第二行开始处理
for i in range(1, n):
for j in range(i+1):
# 当前坐标 (i, j)
if j-1>=0:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
else:
dp[i][j] = dp[i-1][j] + triangle[i][j]
return min(dp[-1])
64-最小路径和-中等
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
'''
每次只能向右或向下
'''
m = len(grid)
n = len(grid[0])
dp = [[math.inf for _ in range(n)]for _ in range(m)]
# 初始化第一行
for i in range(n):
dp[0][i] = grid[0][i]
if i>0:
dp[0][i] += dp[0][i-1]
# 初始化第一列
for i in range(m):
dp[i][0] = grid[i][0]
if i>0:
dp[i][0] += dp[i-1][0]
# 遍历
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
63-不同路径Ⅱ-中等
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
'''
向下或向右
二维dp数组记录到大当前位置有几种路径
'''
# 如果起始位置有石头，直接返回0
if obstacleGrid[0][0] == 1:
return 0
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)]for _ in range(m)]
dp[0][0] = 1
# 初始化第一行
i = 1
while i<n:
if obstacleGrid[0][i] == 1:
break
dp[0][i] = 1
i += 1
while i<n:
dp[0][i] = 0
i += 1
# 初始化第一列
i = 1
while i<m:
if obstacleGrid[i][0] == 1:
break
dp[i][0] = 1
i += 1
while i<m:
dp[i][0] = 0
i += 1
# 遍历
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
elif dp[i-1][j] != 0 and dp[i][j-1] != 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
5-最长回文子串-中等
❌错误的中心扩散法
这样选定中心点，同时向两边扩散，只能处理回文子串为奇数的情况，无法处理偶数的情况，如上述bb
class Solution:
def longestPalindrome(self, s: str) -> str:
'''
中心扩散法
'''
max_len = 1
res = s[0]
n =len(s)
for i in range(n):
left = i-1
right = i+1
while left >=0 and right <= n-1:
if s[left] != s[right]:
break
if right-left+1>max_len:
max_len = right-left+1
res = s[left:right+1]
left -= 1
right += 1
return res
✔ 正确的中心扩散法
考虑当前中心点时，应将左右指针分别移动到不等于中心点处，再向左右扩展
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ''
n = len(s)
cur_len = 1 # ! 初始化为1
max_len = 1
res = s[0]
for i in range(n):
left = i-1
right = i+1
# 向左扩展回文子串
while left>=0 and s[left] == s[i]:
cur_len += 1
left -= 1
# 向右扩展回文子串
while right<=n-1 and s[right] == s[i]:
cur_len += 1
right += 1
# 上面的代码解决当中心点左右两侧与中心点字符相同的情况
# 将left和right移动到与中心点不同的位置
# 左右向两侧扩展
while left >=0 and right <=n-1 and s[left]==s[right]:
cur_len += 2
left -= 1
right += 1
if cur_len > max_len:
max_len = cur_len
res = s[left+1: right]
cur_len = 1
return res
动态规划
class Solution:
def longestPalindrome(self, s: str) -> str:
'''
dp[l][r] 表示字符从l到r是否为回文串
如果要判断dp[l-1][r+1]是否为回文串，必须dp[l][r]是回文，且s[l-1]==s[r+1]
'''
max_len = 0
n = len(s)
if n<2:
return s
res = s[0]
dp = [[False for _ in range(n)]for _ in range(n)]
# 初始化，对角线处为True
for i in range(n):
dp[i][i] = True
# 遍历
# 先枚举子串的长度
for L in range(2, n+1):
# 左边界
for l in range(n):
# 右边界
r = l+L-1
if r>n-1:
break
if s[l] != s[r]:
dp[l][r] = False
else:
if r-l<3: #
标签：int,max,len,力扣,range,prices,全解,动态,dp
From： https://www.cnblogs.com/mudou/p/18315769