62. 不同路径
题目链接： 62. 不同路径 - 力扣（LeetCode）
代码
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]
优化时间复杂度
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [1]*nfor i in range(1,m):for j in range(1,n):dp[j] += dp[j-1]return dp[-1]
63. 不同路径 II
题目链接： 63. 不同路径 II - 力扣（LeetCode）
思路
- dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
- 代码实现：不要忽略第一行和第一列有可能出现障碍的情况
代码
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])# 初始状态data = [[0]*n for _ in range(m)]# 状态转移方程式for i in range(m):if obstacleGrid[i][0] == 1:breakdata[i][0] = 1for j in range(n):if obstacleGrid[0][j] == 1:breakdata[0][j] = 1for i in range(1,m):for j in range(1,n):if obstacleGrid[i][j] == 0:data[i][j] = data[i-1][j] + data[i][j-1]# 终止状态return data[-1][-1]
时间复杂度优化
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])# 初始状态data = [0]*n# 状态转移方程式for j in range(n):if obstacleGrid[0][j] == 1:breakdata[j] = 1for i in range(1,m):for j in range(n):if obstacleGrid[i][j] == 1:data[j] = 0elif j != 0:data[j] += data[j-1]# 终止状态return data[-1]
343. 整数拆分
题目链接： 343. 整数拆分 - 力扣（LeetCode）
思路
- dp[i]的含义是分拆数字i，可以得到的最大乘积为dp[i]
- 本题有点不太好想
代码
class Solution:def integerBreak(self, n: int) -> int:dp = [0]*(n+1)dp[2] = 1for i in range(3,n+1):for j in range(1,i):# j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。dp[i] = max(dp[i],j*dp[i-j],j*(i-j))return dp[-1]
96. 不同的二叉搜索树
题目链接： 96. 不同的二叉搜索树 - 力扣（LeetCode）
思路
- dp[i]的含义是n 个值互不相同的节点组成的二叉搜索树的个数
- 本题难点就是确定递推公式
- 递推关系可以从图中简单看出
代码
class Solution:def numTrees(self, n: int) -> int:dp = [0]*(n+1)dp[0] = 1 #为了方便计算dp[1] = 1for i in range(2,n+1):for j in range(0,i):dp[i] += dp[j]*dp[i-j-1]return dp[-1]
