MinCostClimbingStairs [source code]

public class MinCostClimbingStairs {
static
/******************************************************************************/
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int N = cost.length;
        int[] dp = new int[N + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < dp.length; i++) {
            int curCost = i < cost.length ? cost[i] : 0;
            dp[i] = curCost + Math.min (dp[i - 1], dp[i - 2]);
        }
        return dp[N];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MinCostClimbingStairs.Solution tester = new MinCostClimbingStairs.Solution();
    }
}

题目意思还是很明确的, 标准的DP题目; 题目条件限制了range所以估计是鼓励你可以用recursion来做;

DP问题的核心还是建表, 尤其是表格的entry放的是什么, 当然, 一般得是一个recursive value;

这个题目总体来收还是比较简单的, 一开始我还在纠结是用forward还是backward两个方向来, 但是这题看来forward可以写, 就直接写了; 最后秒杀, 速度是19ms (NA);

不过这题的hint(我写的时候是没有看的)好像是暗示你最好用backward的方向来写; 看起来也可以;

editorial:

class Solution {  
    public int minCostClimbingStairs(int[] cost) {  
        int f1 = 0, f2 = 0;  
        for (int i = cost.length - 1; i >= 0; --i) {  
            int f0 = cost[i] + Math.min(f1, f2);  
            f2 = f1;  
            f1 = f0;  
        }  
        return Math.min(f1, f2);  
    }  
}

一样的思路, 不过是backward, 而且优化了空间复杂度;

关于空间复杂度, 我还是建议你避免Premature Optmization, 实际面试的时候, 你一口气就写出这种过度优化的代码, 人家面试官也未必就对你的印象很好, 而且写代码的时候脑子里始终还要琢磨这些东西, 其实也是在伤害自己的思路. 这种优化, 放到AC之后, 再考虑天剑;

新题目, discussion和submission都没有什么新货;

Problem Description

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

Difficulty:Easy
Total Accepted:7.1K
Total Submissions:15.7K
Contributor:TopCoder111
Companies
amazon
Related Topics
arraydynamic programming
Similar Questions

Hide Hint 1

Say f[i] is the final cost to climb to the top from step i. Then f[i] = cost[i] + min(f[i+1], f[i+2]).