算法|746. 使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

【算法|746. 使用最小花费爬楼梯】示例 1:
输入:cost = [10,15,20] 输出:15 解释:你将从下标为 1 的台阶开始。
  • 支付 15 ,向上爬两个台阶,到达楼梯顶部。 总花费为 15 。
这题是个dp问题,类似普通爬楼梯,不过加了一个体力,就需要比较最值;
dp数组含义:达到此位置的最小体力;
数组初始化:第0阶和第1阶直接花费的体力;
遍历顺序:从前往后;
递推公式:dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
这道题设置的有问题,看似是花费体力去爬,其实只要到达这一层就需要花费cost【i】,并且倒数第二层直接到最后一层不消耗体力,就只能这么写了;
public int minCostClimbingStairs(int[] cost) { if(cost==null||cost.length==0){ return 0; } if(cost.length==1){ return cost[0]; } int[] dp=new int[cost.length]; dp[0]=cost[0]; dp[1]=cost[1]; //初始化 for (int i = 2; i < cost.length; i++) { dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i]; } return Math.min(dp[cost.length-1],dp[cost.length-2]); }

    推荐阅读