文章目录
  1. 1. 题意介绍
    1. 1.1. 题意分析
    2. 1.2. 代码参考

题意介绍

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].

题意分析

这道题是一个动态规划的问题,和上楼梯问题差不多,只不过加了一个代价数组,这道题的关键是找出递归方程,这里我们可以看到此递归方程为:
dp[i] = cost[i] + min(dp[i-1] , dp[i-2]),但这里需要注意一个问题就是最后的结果不是简单的dp[length-1],在这里应该是min(dp[length-1] , dp[length-2]),因为在这里可以一次跨两步,而且没有规定必须最后一步一定是到数组的最后一个元素处。

代码参考

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[0] = cost[0];
dp[1] = cost[1];
// dynamic programming
for (int i=2 ; i<len ; i++){
dp[i] = cost[i] + Math.min(dp[i-1] , dp[i-2]);
}
return Math.min(dp[len-1] , dp[len-2]);
}
}
文章目录
  1. 1. 题意介绍
    1. 1.1. 题意分析
    2. 1.2. 代码参考