<p>You are given an integer array <code>cost</code> where <code>cost[i]</code> is the cost of <code>i<sup>th</sup></code> step on a staircase. Once you pay the cost, you can either climb one or two steps.</p>

<p>You can either start from the step with index <code>0</code>, or the step with index <code>1</code>.</p>

<p>Return <em>the minimum cost to reach the top of the floor</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cost = [10,<u>15</u>,20]
<strong>Output:</strong> 15
<strong>Explanation:</strong> You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cost = [<u>1</u>,100,<u>1</u>,1,<u>1</u>,100,<u>1</u>,<u>1</u>,100,<u>1</u>]
<strong>Output:</strong> 6
<strong>Explanation:</strong> You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= cost.length &lt;= 1000</code></li>
	<li><code>0 &lt;= cost[i] &lt;= 999</code></li>
</ul>

class Solution {
public:
    //simple recusrsion
    int solve(vector<int> &cost, int n){
        //Base Case
        if(n==0)
        {
            return cost[0];
        }

        if(n == 1)
        {
            return cost[1];
        }

        return cost[n] + min(solve(cost, n-1), solve(cost, n-2));
    }

    //recursion + memorization => top -down approch
    int solve2(vector<int>& cost, int n, vector<int>& dp) {
    // Base cases
    if (n == 0) {
        return cost[0];
    }
    if (n == 1) {
        return cost[1];
    }

    // Check if the value is already computed
    if (dp[n] != -1) {
        return dp[n];
    }

    // Recursively compute and store the result in dp
    dp[n] = cost[n] + min(solve2(cost, n - 1, dp), solve2(cost, n - 2, dp));

    return dp[n];
}


    //tabulation => bottom up approch
    int solve3(vector<int> &cost, int n) {
    // If there are less than 2 steps, handle them separately
    if (n == 1) return cost[0];
    
    // Initialize dp array with size n and default values
    vector<int> dp(n);
    dp[0] = cost[0];
    dp[1] = cost[1];

    // Fill dp array from index 2 up to n-1
    for (int i = 2; i < n; i++) {
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
    }

    // The minimum cost to reach the top can come from either the last or second-last step
    return min(dp[n - 1], dp[n - 2]);
}

   //space complexity optimisation 
   int solve4(vector<int> &cost, int n)
   {
    int prev2 = cost[0];
    int prev1 = cost[1];

    for(int i=2; i<n; i++)
    {
        int curr = cost[i] + min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }

    return min(prev1, prev2);
   }


    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // The minimum cost to reach the top can be from either the last or second last step
        // vector<int> dp(n, -1);  // Initialize dp array with -1 (uncomputed)
        
        // return solve3(cost, n);

        return solve4(cost, n);
    }
};

16400