You are given an integer array `cost`

where `cost[i]`

is the cost of `i`

step on a staircase. Once you pay the cost, you can either climb one or two steps.^{th}

You can either start from the step with index `0`

, or the step with index `1`

.

ReturnĀ *the minimum cost to reach the top of the floor*.

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

Example 2:

```
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: 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.
```

Solution:

DP

```
class Solution {
int cache[];
public int minCostClimbingStairs(int[] cost) {
cache = new int[cost.length];
return Math.min(visitStaircase(cost, 0),visitStaircase(cost, 1));
}
public int visitStaircase(int []cost, int index) {
if (index >= cost.length) {
return 0;
}
if(index == cost.length-1) {
return cost[index];
}
if(cache[index] != 0) {
return cache[index];
}
cache[index] = Math.min(cost[index] + visitStaircase(cost, index+1), cost[index] + visitStaircase(cost, index+2));
return cache[index];
}
}
```