文章目录
- 题目介绍
- 题解
题目介绍
题解
思路分析：
- 确定dp数组以及下标的含义：dp[i]的定义为到达第i台阶所花费的最少体力。
- 确定递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。
- dp数组初始化：dp[0] = 0，dp[1] = 0。
- 确定遍历顺序：从递推公式dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])中可以看出，遍历顺序一定是从前向后遍历的。
- 举例推导dp数组。
代码如下：
//cost.length是大于等于2的
class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] dp = new int[len + 1];// 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0dp[0] = 0;dp[1] = 0;// 计算到达“每一层”台阶的最小费用for (int i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[len];}
}
