Leetcode Hot100之多维动态规划
Leetcode Hot100之多维动态规划
依照代码随想录中的动态规划五部曲进行解题:
(1) 确定dp数组(dp table)以及下标的含义
(2) 确定递推公式
(3) 对dp数组进行初始化
(4) 确定遍历顺序(根据地推公式中的依赖关系)
(5) 举例推导dp数组
1. 不同路径
Leetcode 62
- 题目简述
mxn的棋盘格,每一步只能向下或者向右移动,从左上角走到右下角,有多少种路径? - 思路
到达当前点的路径数量 = 到达上方点的路径数量 + 到达左方点的路径数量
dp[i][j] = dp[i-1][j] + dp[i][j-1]
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m < 1 or n < 1:
return 0
dp = [[0] * n for _ in range(m)]
for i in range(n):
dp[0][i] = 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-1][j] + dp[i][j-1]
return dp[m-1][n-1]
2. 最小路径和
Leetcode 64
- 题目简述
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。 - 思路
和最大路径的思路基本一致,相当于在所有的路径中找到和最小的;
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
if n == 0:
return 0
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, n):
dp[0][i] = dp[0][i-1] + grid[0][i]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][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[m-1][n-1]
3. 最长回文子串
Leetcode 5
题目描述
给你一个字符串 s,找到 s 中最长的回文子串。思路
dp[i][j]的含义是字符串s在[i, j]范围内的子串是不是回文串;
有三种情况:
如果是单个字符,那么一定是回文串;
如果是两个字符,那么需要判断s[i]==s[j]
如果是三个及以上的字符,那么需要判断s[i]==s[j] and dp[i+1][j-1]可以看到依赖下左方的dp值,所以遍历顺序应该自下而上,从左往右进行
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return None
dp = [[False] * n for _ in range(n)]
start = 0
end = 0
for i in range(n-1, -1, -1):
for j in range(i, n):
if j == i:
dp[i][i] = True
elif j - i == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i+1][j-1])
# 在循环的过程中记录长度最大的起始坐标
if dp[i][j]:
if j - i > end - start:
end = j
start = i
return s[start : end+1]
4. 最长公共子序列
Leetcode 1143
题目简述
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
abcde和ace的最长公共子序列是ace思路
dp[i][j] 代表text1的前i个字符与text2的前j个字符的最长公共子序列的长度;
为了方便初始化dp数组的长度为(n1+1)*(n2+1),递推公式见下方代码
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n1 = len(text1)
n2 = len(text2)
dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
# 注意当使用dp数组的维度为n+1时,在访问原始的字符串时的index要减1
if text1[i-1] == text2[j-1]:
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
return dp[n1][n2]
5. 编辑距离
Leetcode 72
题目简述
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符思路
dp[i][j]表示word1[:i+1]和word2[:j+1]的编辑距离,当word1[i]不等于word2[j]时,可以进行三种操作:插入,删除,替换,分别对应dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1; 当当word1[i]等于word2[j]时,可以进行三种操作:什么都不做、插入、删除,分别对应dp[i-1][j-1], dp[i][j-1]+1,dp[i-1][j]+1;
为了初始化方便,dp数组的维度也是(n1+1)(n2+1),而不是n1n2
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n1 = len(word1)
n2 = len(word2)
dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
for i in range(1, n2 + 1):
dp[0][i] = i
for i in range(1, n1 + 1):
dp[i][0] = i
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if word1[i-1] != word2[j-1]:
dp[i][j] = min(min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1
else:
dp[i][j] = min(min(dp[i-1][j] + 1, dp[i-1][j-1]), dp[i][j-1] + 1)
return dp[n1][n2]
6. 总结
上面5道题目,可以分成三类:1. 二维表格的路径问题;2. 单个字符串的子串问题; 3. 两个字符串的比较问题;
对于第一类问题,dp数组的形状和二维表格的形状一致,即可模拟路径情况;对于第二类问题,dp数组的两个维度分别表示子串的起始索引;对于第三类,dp数组的两个维度分别表示两个字符串;如果遇到类似问题,可尝试对应的思路;
对于两个字符串的问题,为了初始化方便,往往会使用(n1+1)x(n2+1)维度的dp数组,而不是n1 x n2,这样第0行和第0列分别对应着一个空字符串,也是有实际意义的;