代码随想录算法训练营 Day 28
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 509
前四步：
- 使用一维的dp数组，第i个数（从0开始计算）的斐波那契数值为dp[i]
- 递推公式：F(n) = F(n - 1) + F(n - 2)
- 初始化需要保证F(n - 1)和F(n - 2)有效，因此F(0) = 0, F(1) = 1
- 遍历顺序：从2开始，从前向后遍历
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
return dp[-1]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q2. LeetCode 70
前四步：
- 使用一维dp数组，dp[i]代表达到第i级台阶的方案
- 递推公式：因为可以走一步或者两步，所以需要将$i-1$级（走一步的情况）和$i-2$级（走两步的情况）求和
- 初始化：$dp[0]=1$因为至少需要走一步，$dp[1]=1$因为只能有一种情况（向上走一步），$dp[2]=2$因为有两种情况（向上走两步或者两次向上走一步）
- 遍历顺序：从3开始，从前向后遍历
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q3. LeetCode 746
前四步：
- 使用一维dp数组，dp[i]表示达到第i级台阶的最少开销
- 递推公式：因为可以走一步或者两步，所以需要考虑两种情况，从第$i-1$级上来，花销为$dp[i-1]+cost[i-1]$;从第$i-2$级上来，花销为$dp[i-2]+cost[i-2]$。最后两者取最小值即为dp[i]结果
- 初始化：$dp[0]=0$和$dp[1]=0$，因为我们可以从这两个台阶选择一个开始，不需要开销
- 遍历顺序：从2开始，从前向后遍历（注意我们需要登顶，因此实际应该考虑的是跨过第n台阶的最小开销，dp数组应该大小应该设置为$n+1$）
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[-1]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)