<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:
    //Step 1: Recursive function that will compute the cost to reach a certain step
    
    //Step 2. Recurrence relation to transition between states
    //To reach step n, you could have come from the previous step or from 2 steps before
    //cost(n) = min(cost(n-1),cost(n-2)) + cost[n]
    
    //Step 3. Base Cases
    //n == 0, n == 1 (if started from step 0) and n == 1 (if started from step 1)
    
    //Step 3.
    
    vector<int> memo;
    vector<int> cost;
    
    
    int dp(int n) {
        //base case
        if(n == 0) return cost[0];
        if(n == 1) return cost[1];

        if(memo[n] != -1) return memo[n];
        
        //recursive case
        if(n != cost.size()) memo[n] = min(dp(n-1),dp(n-2)) + cost[n];
        else memo[n] = min(dp(n-1),dp(n-2));
        
        return memo[n];
    }
    
    int minCostClimbingStairs(vector<int>& cost) {
        memo= vector(cost.size() + 1,-1);
        memo[0] = cost[0];
        this->cost = cost;
        
        return dp(cost.size());
    }
};
17100