# LeetCode-746-Min Cost Climbing Stairs

## LeetCode-746-Min Cost Climbing Stairs

Posted by Jae on June 23, 2019

### 1、题目

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor,

and you can either start from the step with index 0, or the step with index 1.

Example 1:

 Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].


Note:

 cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].


### 3、实现

public class Solution {
public static void main(String[] args){
int[] cost = {10, 15, 20};
System.out.println(new Solution().minCostClimbingStairs(cost));
}

// 1、确定状态，一般选区最后一步，当走到顶层i时，可能又i-1层直接上来也可能由i-2层上来
// 2、转移方程 f[i] = min(f[i-1], f[i-2]) + cost[i]
// 3、初始条件 f[0] = cost[0] f[1] = cost[1]
// 4、计算顺序 从2层开始，因为一层和地面的代价都是0
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < len; i++) {
dp[i] = Math.min(dp[i - 1]+ cost[i], dp[i - 2] + cost[i]);
}
return Math.min(dp[len - 1], dp[len - 2]);
}
}


< script src = " / js / bootstrap.min.js " >