Categories
General

Climbing stairs solution – similar to fibonnaci sequence

<?php


class Solution
{

    public static function climbingStairs(int $numberOfStairs)
    {
        $numberOfWays = 0;
        $numberOfWays = self::climbingStairsHelper($numberOfStairs);

        return $numberOfWays;
    }

    public static function climbingStairsHelper($numberOfStairs)
    {
        if ($numberOfStairs <= 0) {
            return 1;
        }
        return self::climbingStairsHelper($numberOfStairs - 1) + self::climbingStairsHelper($numberOfStairs - $numberOfStairs - 2);
    }

    public static function climbingStairsMemoization(int $numberOfStairs)
    {
        $numberOfWays = 0;
        $memo = array();
        for ($i = 0; $i < $numberOfStairs; $i++) {
            $memo[$i] = 0;
        }

        $memo[0] = 0;
        $memo[1] = 2;

        $numberOfWays = self::climbingStairsHelper($numberOfStairs, $memo);

        return $numberOfWays;
    }

    public static function climbingStairsHelperMemoization($numberOfStairs, &$memo)
    {

        if ($numberOfStairs <= 0) {
            return 1;
        }


        return self::climbingStairsHelper($numberOfStairs - 1) + self::climbingStairsHelper($numberOfStairs - $numberOfStairs - 2);
    }

}


//    var_dump(Solution::climbingStairs(2));

var_dump(Solution::climbingStairsMemoization(5));

Leave a Reply