关于leetcode:Leetcode-PHP题解D131-746-Min-Cost-Climbing-Stairs

D131 746. Min Cost Climbing Stairs

题目链接

746. Min Cost Climbing Stairs

题目剖析

给定一个数组，每走一步须要消耗肯定代价。每次能够走1步或2步。寻找走到底所须要的起码步数。

解题思路

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

然而底杰斯特拉应用的是以后最优，因而，如果前面所须要的步数比拟小，这个算法就不实用了。

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

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

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

通过剖析发现，后面的步骤和前面的步骤并没有太大的关系。能够把后面走过的步数，加起来造成新的数组，最初剩下两个元素中最小的那个便是起码步数。

最终代码

<?phpclass 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]);    }}

若感觉本文章对你有用，欢送用爱发电赞助。