LeetCode 746. Min Cost Climbing Stairs

题目:爬楼梯,可以选择爬一级或者两级,每一级需要消耗的能量存储在cost数组中,可以选择从第一级或者第二级开始爬,求最小的能量消耗是多少。

思路:
非常简单的一道动归题目,只需要用到缓存,就能直接解决了。唯一我用到的一个技巧:因为要爬到最上面,意味着要爬过最后一级台阶,那么我向数组里push一个消耗为0的台阶,作为最终目标。没有多想,直接开码:

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    cost.push(0);
    let target = cost.length - 1, memo = {};

    if (target < 2) {
        return Math.min(...cost);
    }
    let r = function (i) {
        if (memo[i]) return memo[i];
        if (i > 1) {
            memo[i] = Math.min(r(i - 1) + cost[i], r(i - 2) + cost[i]);
        } else {
            memo[i] = cost[i];
        }
        return memo[i];
    };

    return r(target);
};
分类: 算法

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注