动态规划解析：以最小花费爬楼梯为例

动态规划的核心思想

动态规划（DP）通过将复杂问题分解为相互重叠的子问题，并存储子问题的解（避免重复计算），最终高效求解原问题。它适用于具有以下特征的问题：

1. 重叠子问题：子问题被重复计算多次。

2. 最优子结构：问题的最优解包含子问题的最优解。

动态规划的解题步骤

1. 定义状态：用数组 dp[i] 表示到达第 i 级台阶的最小花费。

2. 确定状态转移方程：基于子问题关系推导递推式。

3. 设置初始条件：初始化基础状态（如 dp[0], dp[1]）。

4. 迭代计算：按顺序从小问题向大问题递推。

实例分析：LeetCode 746. 最小花费爬楼梯

问题描述
给定整数数组 cost，cost[i] 表示踏上第 i 级台阶的代价。每次可以爬 1 或 2 级台阶，求到达顶部（数组末尾之后）的最小花费。

关键思路

• 状态定义：dp[i] 表示到达第 i 级台阶的最小花费（注意：顶部是第 n 级，n = cost.length）。

• 状态转移：
  到达第 i 级有两种方式：

  1. 从第 i-1 级爬 1 步：花费 = dp[i-1] + cost[i-1]

  2. 从第 i-2 级爬 2 步：花费 = dp[i-2] + cost[i-2]
     取两者最小值：
     dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

• 初始条件：

  • 起点为第 0 级或第 1 级（花费为 0）：
    dp[0] = 0, dp[1] = 0

• 目标：计算 dp[n]（n 是台阶总数）。

示例说明
若 cost = [10, 15, 20]：

• dp[0] = 0, dp[1] = 0（初始站在第0或第1级）

• dp[2] = min(0+10, 0+15) = 10（从第0级跨2步）

• dp[3] = min(10+15, 0+20) = 20（从第1级跨2步）

• 最小花费为 dp[3] = 20。

  class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n + 1]; // dp[i] 表示到达第 i 级的最小花费 dp[0] = 0; // 初始站在第0级，花费0 dp[1] = 0; // 初始站在第1级，花费0 for (int i = 2; i <= n; i++) { // 从 i-1 级爬1步，或从 i-2 级爬2步 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[n]; // 到达顶部（第n级）的最小花费 }}

  复杂度分析

• 时间复杂度：$O(n)$，遍历一次数组。

• 空间复杂度：$O(n)$，使用长度为 $n+1$ 的 DP 数组。

优化空间复杂度

实际只需保留前两个状态，将空间优化至 $O(1)$：

class Solution { public int minCostClimbingStairs(int[] cost) { int a = 0, b = 0; // a = dp[i-2], b = dp[i-1] for (int i = 2; i <= cost.length; i++) { int c = Math.min(b + cost[i - 1], a + cost[i - 2]); a = b; // 更新前两级状态 b = c; // 更新前一级状态 } return b; }}

动态规划的适用场景

1. 最值问题：如最短路径、最小花费。

2. 计数问题：如路径总数。

3. 序列决策问题：如背包问题、股票买卖。

掌握动态规划的核心在于识别子问题关系，并通过状态转移方程将问题拆解为可管理的部分。通过练习经典问题（如爬楼梯、背包问题），能逐步培养DP思维！