力扣746：三步通关最小花费爬楼梯
2周前 (05-16)
题目解析：
站在楼梯的某个台阶时，需要支付当前台阶对应的体力值cost[i]，之后可以选择向上爬1或2个台阶。最终目标是到达楼层顶部（即数组末尾之后的位置），且初始位置可选择下标0或1的台阶作为起点。要求找出到达顶部的最小花费路径。例如输入cost=[10,15,20]时，最佳路径是从索引1出发直接跨两步到顶部，总花费15。
解题思路与过程：
1.关键逻辑拆解
状态定义：dp[i]表示到达索引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循环内的条件语句增加了代码复杂度。
代码+注释：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int dp[1001]; // 假设cost长度<=1000，避免动态内存分配
dp[0] = cost[0]; // 必须支付cost[0]才能站在第0级台阶
dp[1] = cost[1]; // 同理，支付cost[1]后才能站在第1级
dp[2] = min(dp[0], dp[1]); // 到达第2级的最小花费为前两步的较小值
for(int i = 3; i <= cost.size(); i++) { // 从第3级开始推导到顶部
if(i-1 != 2) { // 非特殊位置时的通用递推
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
} else { // 处理i=3时的特殊边界情况
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]);
}
}
return dp[cost.size()]; // 返回到达顶部的最小花费
}
};原创内容 转载请注明出处
