62.不同路径
力扣链接
动态规划5步曲
- 确定dp数组（dp table）以及下标的含义： dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
- 确定递推公式，dp[i][j] = dp[i - 1][j] + dp[i][j - 1] i>0,j>0
- dp数组如何初始化
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
- 确定遍历顺序【dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。】
- 举例推导dp数组
时间复杂度：O(m × n) 空间复杂度：O(m × n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0]*n for _ in range(m)] ## 创建一个二维列表用于存储唯一路径数
# 设置第一行和第一列的基本情况
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 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]
递归法
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1
return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)
63. 不同路径 II
力扣链接
动态规划5步曲
- 确定dp数组（dp table）以及下标的含义：dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
- 确定递推公式，dp[i][j] = dp[i - 1][j] + dp[i][j - 1] i>0,j>0
- dp数组如何初始化 【但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。】
- 确定遍历顺序【dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。】
- 举例推导dp数组
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid) #行数
n = len(obstacleGrid[0]) #列数
if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
return 0
dp = [[0]*n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0: # 遇到障碍物时，直接退出循环，后面默认都是0
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
for i in range(1, m):
for j in range(1,n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
343. 整数拆分 （可跳过）
力扣链接
动态规划5步曲
- 确定dp数组（dp table）以及下标的含义： dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
- 确定递推公式，
可以想 dp[i]最大乘积是怎么得到的呢？【拆成2个，拆成3个以上】
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
j从1开始遍历，dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));- dp数组如何初始化 【dp[2]=1 】
- 确定遍历顺序【从前往后遍历】
- 举例推导dp数组【1<=j <=i-2】
时间复杂度：O(n^2) 空间复杂度：O(n)
class Solution:
# 假设对正整数 i 拆分出的第一个正整数是 j（1 <= j < i），则有以下两种方案：
# 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)
# 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]
def integerBreak(self, n):
dp = [0] * (n + 1) # #dp[n]: n拆分的整数的乘积的最大值.
dp[2] = 1 # 初始化dp[2]为1，因为当n=2时，只有一个切割方式1+1=2，乘积为1
# 从3开始计算，直到n
for i in range(3, n + 1):
# 遍历所有可能的切割点
for j in range(1, i // 2 + 1):
# 计算切割点j和剩余部分(i-j)的乘积，并与之前的结果进行比较取较大值
dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
return dp[n] # 返回最终的计算结果
96.不同的二叉搜索树 （可跳过）
力扣链接
动态规划5步曲
- 确定dp数组（dp table）以及下标的含义： dp[n]：n个节点，组成的二叉树种类。
- 确定递推公式，dp[n] = dp[n-1]*dp[0]+dp[n-2]*dp[1]+dp[n-3]*dp[2]+…+dp[0]*dp[n-1]
- dp数组如何初始化 【dp[0]=1 】
- 确定遍历顺序【那么遍历i里面每一个数作为头结点的状态，用j来遍历】
- 举例推导dp数组
时间复杂度：$O(n^2)$ 空间复杂度：$O(n)$
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1) #dp[n]表示由n个节点组成的二叉搜索树的种类
dp[0] = 1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1
for i in range(1,n+1): # 遍历从1到n的每个数字
for j in range(0, i): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量
dp[i] += dp[j]*dp[i-j-1] # 利用动态规划的思想，累加左子树和右子树的组合数量
return dp[n]
