动态规划#

本节介绍动态规划的基本概念与入门题目，包括斐波那契数列、爬楼梯系列等经典问题。

动态规划基础#

动态规划（DP）用于将一个复杂问题分解为多个子问题，通过缓存子问题的结果避免重复计算。

✅ 通用步骤#

定义状态：用一个变量/数组 dp[i] 表示问题的某个子结构。
状态转移方程：通过子问题之间的关系推导 dp[i]。
初始化：设定初始条件，即最小子问题的结果。
确定遍历顺序：一般为从小到大、递推形式。
返回最终结果：通常为 dp[n]、dp[n-1] 等。

509. 斐波那契数#

LeetCode 509. Fibonacci Number

状态定义：dp[i] 表示第 i 个斐波那契数；
状态转移：dp[i] = dp[i-1] + dp[i-2]；
空间优化：只用两个变量即可。

1
class Solution:
2
    def fib(self, n: int) -> int:
3
        if n == 0 or n == 1:
4
            return n
5
        dp1 = 1  # 表示 dp[i - 1]
6
        dp2 = 0  # 表示 dp[i - 2]
7
        for i in range(2, n + 1):
8
            temp = dp1 + dp2
9
            dp2 = dp1
10
            dp1 = temp
11
        return dp1

70. 爬楼梯#

LeetCode 70. Climbing Stairs

状态定义：dp[i] 表示到达第 i 个台阶的方法数；
状态转移：dp[i] = dp[i-1] + dp[i-2]；
初始条件：dp[1] = 1, dp[2] = 2。

1
class Solution:
2
    def climbStairs(self, n: int) -> int:
3
        if n <= 1:
4
            return n
5
        dp = [0] * (n + 1)
6
        dp[1] = 1
7
        dp[2] = 2
8
        for i in range(3, n + 1):
9
            dp[i] = dp[i - 1] + dp[i - 2]
10
        return dp[n]

746. 使用最小花费爬楼梯#

LeetCode 746. Min Cost Climbing Stairs

状态定义：dp[i] 表示到达第 i 层的最小花费；
状态转移：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])；
初始条件：dp[0] = 0, dp[1] = 0。

1
class Solution:
2
    def minCostClimbingStairs(self, cost: List[int]) -> int:
3
        dp = [0] * (len(cost) + 1)
4
        # 到达第0级和第1级的花费都是0
5
        dp[0] = 0
6
        dp[1] = 0
7
        for i in range(2, len(cost) + 1):
8
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
9
        return dp[len(cost)]