D131 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]);
}
}
若觉得本文章对你有用，欢迎用爱发电资助。
