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

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