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

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

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

扩展阅读

加个好友，技术交流