力扣746：三步通关最小花费爬楼梯
https://www.xinaozhilu.cn/zb_users/upload/2025/05/202505141747200078707333.jpg题目解析：站在楼梯的某个台阶时，需要支付当前台阶对应的体力值cost，之后可以选择向上爬1或2个台阶。最终目标是到达楼层顶部（即数组末尾之后的位置），且初始位置可选择下标0或1的台阶作为起点。要求找出到达顶部的最小花费路径。例如输入cost=时，最佳路径是从索引1出发直接跨两步到顶部，总花费15。解题思路与过程：1.关键逻辑拆解 状态定义：dp表示到达索引i台阶时的最小累计花费。 初始化设定： dp=cost（必须支付cost才能站在第0级） dp=cost（同理必须支付cost才能站在第1级） dp=min(dp,dp)（到达索引2时可选前两步中更优路径）2.循环递推： 从i=3开始遍历到cost.size()（即楼梯顶部） 特殊处理i=3：当i-1 == 2时，说明当前处于索引3，此时比较前一步总花费+cost与前两步总花费的最小值 一般情况：其他位置比较前一步总花费+cost与前两步总花费+cost算法特点1.反向递推终点：最终返回dp，该位置代表楼梯外的顶部，其值由前面的递推关系决定。2.边界条件优化：通过提前处理dp减少后续分支判断，但for循环内的条件语句增加了代码复杂度。代码+注释：<i><i>class Solution {public:
int minCostClimbingStairs(vector<int>& cost) {
int dp; // 假设cost长度<=1000，避免动态内存分配
dp = cost; // 必须支付cost才能站在第0级台阶
dp = cost; // 同理，支付cost后才能站在第1级
dp = min(dp, dp); // 到达第2级的最小花费为前两步的较小值
for(int i = 3; i <= cost.size(); i++) { // 从第3级开始推导到顶部
if(i-1 != 2) { // 非特殊位置时的通用递推
dp = min(dp + cost, dp + cost);
} else { // 处理i=3时的特殊边界情况
dp = min(dp + cost, dp);
}
}
return dp; // 返回到达顶部的最小花费
}
};</i></i>原文：https://www.xinaozhilu.cn/list/15.html
页:
[1]