代码随想录算法训练营 Day 29
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 62
前四步：
- 使用二维的dp数组，dp[i][j]代表走到当前位置$(i,j)$的路径数量
- 递推公式：dp[i][j] = dp[i - 1][j]（从左边位置向右走一步）+ dp[i][j - 1]（从上方位置向下走一步）
- 初始化：因为只能向右或向下走，因此第一行和第一列的初始值为1
- 遍历顺序：从(1, 1)开始遍历整个数组
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
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[-1][-1]
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m \times n$)
Q2. LeetCode 63
前四步：
- 使用二维dp数组，dp[i][j]代表达到当前位置$(i,j)$的路径数
- 递推公式：1. 当前位置不为障碍物：dp[i][j] = dp[i - 1][j]（左边位置向右走一步） + dp[i][j - 1]（上方位置向下走一步）; 2. 当前位置为障碍物：dp[i][j] = 0（无法经过该位置，路径数为0）
- 初始化：因为只能向右或向下走，因此第一行和第一列的初始值为1。但还需要考虑出现障碍物的情况，如果出现障碍物，那么当前位置和后续位置都等于0，因为无法走到该位置了
- 遍历顺序：从$(1,1)$开始遍历整个数组
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] != 1:
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] != 1:
dp[0][j] = 1
else:
break
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m \times n$)
Q3. LeetCode 343
前四步：
- 使用一维dp数组，dp[i]表示和为i时的最大积
- 递推公式：dp[i] = max(dp[i], j * (i - j), j * dp[i - j])。j的取值范围为[1, i - 1]（可以将i拆分为两数之和）
- 初始化：$dp[0]=0$和$dp[1]=0$，因为我们可以从这两数无法分解为两个正整数；$dp[2]=1$
- 遍历顺序：从3开始，从前向后遍历，并且每一步在开始一个循环，更新当前最大值
递推公式理解：计算j * (i - j)代表当前将i划分为两数之和，而j * dp[i - j]代表当前将i划分为多数之和，因为dp[i - j]已经更新为数字i - j的最大积
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i - 1):
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
return dp[-1]
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n$)
Q4. LeetCode 96
五部曲：
- 使用一维dp数组，dp[i]代表i个有序数字可以组成的二叉搜索树的个数
- 递推公式：dp[i] += dp[j - 1] * dp[i - j]. 具体解释：j的取值范围是[1, i], 代表当前头节点的数值为j，那么[1, j - 1]就是左子树，[j + 1, i]就是右子树，转化为两个子问题（j - 1/i - j个有序数字可以组成二叉搜索树的个数）
- 初始化：$dp[0] = 1$，空二叉树
- 遍历顺序：j - 1/i - j一定是小于i的，因此从前向后遍历
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[-1]
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n$)