关于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层”，嵌套层数过多的谬误。

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

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

最终代码

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

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