# Min Cost Climbing Stairs LeetCode Solution

Difficulty Level Easy
Array Dynamic ProgrammingViews 2361

## Problem Statement

Min Cost Climbing Stairs LeetCode Solution – An integer array `cost`  is given, where `cost[i]` is the cost of `i`th 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.
```

Constraints:

• `2 <= cost.length <= 1000`
• `0 <= cost[i] <= 999`

## Approach

1. The Main idea of this problem is to use Dynamic Programming to find minimum cost climbing stairs.

2. We will discuss recursion with memoization as it is beginner-friendly.

3. Now, rec(i) is the minimum cost to the `i`th step. we can take one step or two-step from index i.

4. Now, recurrence will be rec(i)=cost[i]+min(rec(i+1),rec(i+2))

5. Base condition will be rec(i)=0 if i>=n where n is the length of the array or our estimated path because we reach the destination so no further movement is possible.

## Code:

### C++ Leetcode Solution:

```class Solution {
public:
#define ll int
ll dp;
ll n;
ll rec(ll i,vector<ll>&a)
{
if(i>=n)
return 0;
ll &ans=dp[i];
if(ans!=-1)
return ans;
ans=a[i]+min(rec(i+2,a),rec(i+1,a));

return ans;

}
int minCostClimbingStairs(vector<int>& cost) {
memset(dp,-1,sizeof(dp));
n=cost.size();

return min(rec(1,cost),rec(0,cost));
}
};```

### Java Leetcode Solution:

```class Solution {
int rec(int i,int n,int [] a,int[] dp)
{

if(i>=n)
return 0;

if(dp[i]!=-1)
return dp[i];
dp[i]=a[i]+Math.min(rec(i+2,n,a,dp),rec(i+1,n,a,dp));

return (int)dp[i];

}
public int minCostClimbingStairs(int[] cost) {
int n=cost.length;
int[] dp = new int[n+11];
Arrays.fill(dp, -1);
int a=rec(0,n,cost,dp);
int b=rec(1,n,cost,dp);
return (int)(Math.min(a,b));
}
}```

## Complexity Analysis of Min Cost Climbing Stairs Leetcode Solution:

### Time Complexity

Time complexity will be o(n). Because we are traversing the whole array.

### Space Complexity

Space complexity will be o(n). We are creating dp table of length n to store the value in every index.

Translate »