Python刷题模板——动态规划

解题思路

核心问题:穷举

关键元素:重叠子问题、最优子结构、状态转移方程

动态规划问题最困难的就是写出这个暴力解,即状态转移方程,优化方法无非是用备忘录或者 DP table。

解决重叠子问题

1.设置备忘录,记录子问题的答案(相当于剪枝)(自顶向下、递归)

509. 斐波那契数

2.DP table,状态转移方程(自底向上、迭代)

f(n)=f(n-1)+f(n-2)

状态压缩

1.斐波那契数中只需要前两个状态,不需要那么长的DP table

2.最长回文子序列,每个位置的值只与周围的值有关。因此将二维DP数组降为一维DP数组。

最优子结构

1.子问题之间必须互相独立

2.改造问题,使其具有最优子结构

状态转移方程

1.确定base case

2.确定状态(原问题和子问题中会变化的变量)

3.确定选择(导致「状态」产生变化的行为)

4.明确dp函数(参数:状态,返回值:题目要求计算的量)

数学归纳思想找状态转移方程

1.明确 dp 数组所存数据的含义

2.根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0…i-1] 都已知,想办法求出 dp[i]

子序列类问题

解题模板

# 一维DP数组
# dp[i]为以nums[i]为结尾的目标子序列长度
for i in range(len(nums)):
    for j in range(i):
        dp[i] = 最值(dp[i],dp[j] + ...)
        
# 二维DP数组
# 1. dp[i][j]为s1[0...i]和s2[0...j]中的目标子序列(最长公共子序列、编辑距离)
# 2. dp[i][j]为s[i...j]中的目标子序列(最长回文子序列)
m,n = len(s1),len(s2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
... # 处理 base case
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] + ...
        else:
            dp[i][j] = 最值(...)

最长递增子序列 LIS

动态规划 or 二分查找(纸牌游戏)

300. 最长上升子序列

二维递增子序列:信封嵌套问题

354. 俄罗斯套娃信封问题

最大子数组问题

dp[i]为以nums[i]为结尾的最大子数组和

53. 最大子序和

最长公共子序列LCS

dp[i,j]为[0…i-1]与[0…j-1]的LCS长度

1143. 最长公共子序列

583. 两个字符串的删除操作

dp[i,j]为[0…i-1]与[0…j-1]的最小ASCII删除和

712. 两个字符串的最小ASCII删除和

编辑距离(实用)

dp[i,j]为[0…i-1]与[0…j-1]的最小编辑距离

72. 编辑距离

712. 两个字符串的最小ASCII删除和

最长回文子序列

dp[i,j]为[i…j]最长回文子序列长度

516. 最长回文子序列

最小代价构造回文串

dp[i,j]为[i…j]变成回文的最少插入次数

1312. 让字符串成为回文串的最少插入次数

其他经典问题

正则表达式

dp[i,j]为string[0…i-1]能否与pattern[0…j-1]匹配

高楼扔鸡蛋

dp(K,N)为K个鸡蛋,楼层数N

basecase: K=1, N=0

运用二分查找来优化线性搜索

发表评论