D131 746. Min Cost Climbing Stairs

Topic link

746. Min Cost Climbing Stairs

Subject analysis

Given an array, each step costs something. Take one or two steps at a time. Find the minimum number of steps you need to take to get to the end.

Their thinking

The first idea was to use Dijkstra.

However, Dijkstra uses the current best, so if the number of steps required later is small, this algorithm does not apply.

The second thing that comes to mind is a recursive approach.

Try two for every step you take, one step and two steps. It worked fine for some short arrays, but there was a Time exceed error after committing the code. After local debugging, “the number of nesting layers reaches the highest 256 layers”, the error of too many nesting layers.

So I started analyzing if there was a better algorithm.

Through analysis, it is found that the previous steps and the following steps do not have much relationship. You can add up the number of previous steps to form a new array, and the smallest of the two remaining elements is the least number of steps.

The final code

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

If you find this article useful, you are welcome to subsidize it with love.