# 746. Min Cost Climbing Stairs

You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps.

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];
}
}``````

https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&id=dynamic-programming