力扣746：三步通关最小花费爬楼梯

19339201706

题目解析：

站在楼梯的某个台阶时，需要支付当前台阶对应的体力值cost，之后可以选择向上爬1或2个台阶。最终目标是到达‌楼层顶部‌（即数组末尾之后的位置），且初始位置可选择下标0或1的台阶作为起点。要求找出到达顶部的‌最小花费路径‌。例如输入cost=[10,15,20]时，最佳路径是从索引1出发直接跨两步到顶部，总花费15。

解题思路与过程：

1.关键逻辑拆解

    ‌状态定义‌：dp表示到达索引i台阶时的最小累计花费。

‌    初始化设定‌：

        dp[0]=cost[0]（必须支付cost[0]才能站在第0级）

        dp[1]=cost[1]（同理必须支付cost[1]才能站在第1级）

        dp[2]=min(dp[0],dp[1])（到达索引2时可选前两步中更优路径）

2‌.循环递推‌：

    从i=3开始遍历到cost.size()（即楼梯顶部）

    ‌特殊处理i=3‌：当i-1 == 2时，说明当前处于索引3，此时比较前一步总花费+cost[i-1]与前两步总花费的最小值

    ‌一般情况‌：其他位置比较前一步总花费+cost[i-1]与前两步总花费+cost[i-2]

算法特点

‌1.反向递推终点‌：最终返回dp[cost.size()]，该位置代表楼梯外的顶部，其值由前面的递推关系决定。

‌2.边界条件优化‌：通过提前处理dp[2]减少后续分支判断，但for循环内的条件语句增加了代码复杂度。

代码+注释：

1. <i><i>class Solution {
   
2. public:
   
3.     int minCostClimbingStairs(vector<int>& cost) {
   
4.         int dp[1001]; // 假设cost长度<=1000，避免动态内存分配
   
5.         dp[0] = cost[0]; // 必须支付cost[0]才能站在第0级台阶
   
6.         dp[1] = cost[1]; // 同理，支付cost[1]后才能站在第1级
   
7.         dp[2] = min(dp[0], dp[1]); // 到达第2级的最小花费为前两步的较小值
   
8.         
   
9.         for(int i = 3; i <= cost.size(); i++) { // 从第3级开始推导到顶部
   
10.             if(i-1 != 2) { // 非特殊位置时的通用递推
    
11.                 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
    
12.             } else { // 处理i=3时的特殊边界情况
    
13.                 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]);
    
14.             }
    
15.         }
    
16.         return dp[cost.size()]; // 返回到达顶部的最小花费
    
17.     }
    
18. };</i></i>

复制代码

原文：https://www.xinaozhilu.cn/list/15.html