Leetcode PHP题解--D131 746. Min Cost Climbing Stairs


题目链接

746. Min Cost Climbing Stairs

题目分析

给定一个数组,每走一步需要耗费一定代价。每次可以走1步或2步。寻找走到底所需要的最少步数。

解题思路

一开始想到的是用底杰斯特拉(Dijkstra)算法。

然而底杰斯特拉使用的是当前最优,因此,如果后面所需要的步数比较小,这个算法就不适用了。

其次想到的是递归的方法。

每走一步都尝试两种,即一步和两步。对一些短的数组能顺利执行,但是,提交代码后出现了Time exceed的错误。在本地调试之后出现了“嵌套层数到达最高层256层”,嵌套层数过多的错误。

于是开始分析有没有更优的算法。

通过分析发现,前面的步骤和后面的步骤并没有太大的关系。可以把前面走过的步数,加起来形成新的数组,最后剩下两个元素中最小的那个便是最少步数。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $cost
     * @return Integer
     */
    protected $minimumCost = PHP_INT_MAX;
    function minCostClimbingStairs($cost) {
        $costBySteps = [];
        foreach($cost as $key => $value){
            if($key<2){
                continue;
            }
            $cost[$key] += min($cost[$key-1], $cost[$key-2]);
        }
        $amount = count($cost);

        return min($cost[$amount-1], $cost[$amount-2]);
    }
}

若觉得本文章对你有用,欢迎用爱发电资助。


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: 你真的了解 sync.Once 吗

>> 下一篇: Leetcode PHP题解--D132 7. Reverse Integer