746. Min Cost Climbing Stairs

一时失言乱红尘 2022-05-26 23:07 131阅读 0赞

数组的每个索引做为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 cost\[i\](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

/** * Created by Joe on 2018/4/7. * 746. Min Cost Climbing Stairs * https://leetcode.com/problems/min-cost-climbing-stairs/description/ */
    public class P746 { 
        public int minCostClimbingStairs(int[] cost) {
            return Math.min(getCost(cost, 0), getCost(cost, 1));
        }
    
        private int getCost(int[] cost, int i) {
            if (i >= cost.length) return 0;
    
            return cost[i] + Math.min(getCost(cost, i + 1), getCost(cost, i + 2));
        }
    }

最开始的代码，提示是在最后一个测试用例超时了。

之后看了讨论区，都说是用DP。

还是对题目缺乏思考：**只要发现划分成子任务是非独立的任务，即每一个子任务都需要依赖其他子任务的结果时候，就应该考虑使用DP**。

代码：

public int minCostClimbingStairs(int[] cost) {
        if(cost == null)
            return 0;
        if(cost.length == 1)
            return cost[0];
        if(cost.length == 2)
            return Math.min(cost[0],cost[1]);
        int[] tmp = new int[cost.length];//记录着必须选择第i阶台阶时，最小代价
        tmp[0] = cost[0];
        tmp[1] = cost[1];
        for(int i = 2; i < tmp.length; i++) {
            tmp[i] = Math.min(tmp[i - 2], tmp[i - 1]) + cost[i];
        }
        return Math.min(tmp[tmp.length - 1], tmp[tmp.length - 2]); //最后一步可以从最后一个台阶或者倒数第二个台阶跨越
    }