SONG Shengjie
List: 理论基础，509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯
理论基础，509.斐波那契数fibonacci-number，70. 爬楼梯climbing-stairs，746. 使用最小花费爬楼梯min-cost-climbing-stairs
理论基础
509.斐波那契数fibonacci-number
class Solution:
def fib(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 0
if n >= 1:
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
70. 爬楼梯climbing-stairs
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[n]
746. 使用最小花费爬楼梯min-cost-climbing-stairs
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0] * (len(cost) + 1)
for i in range(2, len(cost) + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[-1]