代码随想录算法训练营Day34

力扣746.使用最小花费爬楼梯【easy】
力扣62.不同路径【medium】
力扣63.不同路径Ⅱ【medium】
力扣343.整数拆分【medium】
力扣96.不同的二叉搜索树【medium】

一、力扣746.使用最小花费爬楼梯【easy】

题目链接：力扣746.使用最小花费爬楼梯

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 和前面几道题思路一致，要将问题转化成子问题

• 

• 

• 时间复杂度：$O(n)$

• 空间复杂度：前两个$O(n)$ ，第三个优化到 $O(1)$

2、代码

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)# def dfs(i):#     if i <= 1 :#         return 0#     res = min(dfs(i - 1) + cost[i -1], dfs(i - 2) + cost[i - 2])#     return res# return dfs(n)# @cache# def dfs(i):#     if i <= 1:#         return 0#     res = min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2])#     return res# return dfs(n)# dp = [0] * (n + 1)# dp[0] = dp[1] = 0 # for k in range(2, n + 1):#     dp[k] = min(dp[k - 1] + cost[k - 1], dp[k - 2] + cost[k - 2])# return dp[n]f0 = f1 = 0for i in range(1,n):new_f = min(f0 + cost[i - 1], f1 + cost[i])f0 = f1f1 = new_freturn f1

---

二、力扣62.不同路径【medium】

题目链接：力扣62.不同路径

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 转为子问题

  • 

• 明确 $dp[i][j]$ 的含义：表示从 $(0,0)$ 到 $(i,j)$ 的路径数

• 状态方程：$dp[i][j]=dp[i-1][j]+dp[i][j-1]$

• 边界 / 初始值：

  • 用递归时：$dfs(-1,j)=dfs(i,-1)=0,dfs(0,0)=1$
  • 转成dp是：有两种处理方式，生成的矩阵的大小不一致
    • $dp[0][1]=1$
    • $dp[i][0]=dp[0][j]=1$

• 时间复杂度：$O(m\ast n)$ 状态个数 * 单个状态的计算时间

2、代码

class Solution:def uniquePaths(self, m: int, n: int) -> int:# @cache# def dfs(i, j):#     if i < 0 or j < 0:#         return 0#     if i == 0 and j == 0:#         return 1#     return dfs(i, j - 1 ) + dfs(i - 1, j)# return dfs(m - 1, n - 1)# dp = [[0] * (n + 1) for _ in range(m + 1)]# dp[0][1] = 1# for i in range(m):#     for j in range(n):#         dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]# return dp[m][n]dp = [[0] * n for _ in range(m) ]for i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 1for 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]

---

三、力扣63.不同路径Ⅱ【medium】

题目链接：力扣63.不同路径Ⅱ
left =x300
视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 多了障碍物，其他与62一致
• 碰到障碍物，不可以走，意思就是无效路径，之前的也白搭
• 所以碰到障碍，$dp[i][j]=0$
• 时间复杂度：$O(m\ast n)$ 状态个数 * 单个状态的计算时间

2、代码

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * (n + 1) for _ in range(m + 1)]dp[0][1] = 1for i, row in enumerate(obstacleGrid):for j, x in enumerate(row):if x == 0:dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]return dp[m][n]

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])@cachedef dfs(i,j):if i < 0 or j < 0 or obstacleGrid[i][j]:return 0if i == 0 and j == 0 :return 1return dfs(i - 1, j) + dfs(i, j - 1)return dfs(m - 1, n - 1)

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]for i in range(m):if obstacleGrid[i][0] == 0:  # 遇到障碍物时，直接退出循环，后面默认都是0dp[i][0] = 1else:breakfor j in range(n):if obstacleGrid[0][j] == 0:dp[0][j] = 1else:breakfor i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 1:continuedp[i][j] = dp[i - 1][j] + dp[i][j - 1]return dp[m - 1][n - 1]

3、代码问题

• 

---

四、力扣343.整数拆分【medium】

题目链接：力扣343.整数拆分

视频链接：代码随想录
题解链接：Krahets

1、思路

• 利用均值不等式说明 当取等时，乘机最大
• 
• 
• 时间复杂度：$O(1)$
• 

2、代码

class Solution:def integerBreak(self, n: int) -> int:if n <= 3:return n - 1a, b = n // 3, n % 3if b == 0:return int(math.pow(3,a))if b == 1:return int(math.pow(3, a - 1) * 4)if b == 2:return int(math.pow(3, a) * 2)

---

五、力扣96.不同的二叉搜索树【medium】

题目链接：力扣96.不同的二叉搜索树

视频链接：代码随想录
题解链接：画手大鹏

1、思路

• $dp[n]$：n个结点存在二叉排序树的个数

• $f(i)$：以i为根的二叉搜索树的个数

• 卡特兰公式：$C_n={\sum }_{i=0}^{n-1}{C}_i\cdot C_{n-i-1}\text{（对任意 }n\ge 1\text{ 成立）}$

• 

• 时间复杂度：$O(n^2)$

2、代码

class Solution:def numTrees(self, n: int) -> int:dp = [0] * (n + 1)dp[0] = 1for i in range(1,n + 1):for j in range(1, i + 1):dp[i] += dp[j-1] * dp[i - j]return dp[n]

---