代码随想录算法训练营第33天|62.不同路径63.不同路径II343.整数拆分96.不同的二叉搜索树

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]*n for 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: break data[i][0] = 1 for j in range(n): if obstacleGrid[0][j] == 1: break data[0][j] = 1 for 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: break data[j] = 1 for i in range(1,m): for j in range(n): if obstacleGrid[i][j] == 1: data[j] = 0 elif 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] = 1 for 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] = 1 for i in range(2,n+1): for j in range(0,i): dp[i] += dp[j]*dp[i-j-1] return dp[-1]