# 746. Min Cost Climbing Stairs

Mon Mar 20 2023 20:13:44 GMT+0000 (Coordinated Universal Time)

Saved by @Ranjan_kumar #c++

```//////Top-Down approach / recursion-memoization////
class Solution {
public:

int solve(vector<int>& cost, int n, vector<int> &dp)
{
if(n==0) return cost[0];
if(n==1) return cost[1];
if(dp[n]!=-1) return dp[n];
dp[n]=min(solve(cost, n-1,dp),solve(cost, n-2, dp))+cost[n];
return dp[n];
}

int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n+1, -1);
int ans=min(solve(cost, n-1, dp),solve(cost, n-2, dp));
return ans;
}
};

/////Tabulation / bottom-up approach/////
class Solution {
public:

int solve(vector<int>& cost, int n)
{
vector<int> dp(n+1, -1);
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<n;i++)
{
dp[i]=min(dp[i-1],dp[i-2])+cost[i];
}
return min(dp[n-1], dp[n-2]);
}

int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();

return solve(cost, n);
}
};

////////space optimization///////
class Solution {
public:

int solve(vector<int>& cost, int n)
{
int pr1=cost[0], pr2=cost[1], curr;
for(int i=2;i<n;i++)
{
curr=min(pr1,pr2)+cost[i];
pr1=pr2;
pr2=curr;
}
return min(pr1, pr2);
}

int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();

return solve(cost, n);
}
};```
content_copyCOPY

https://leetcode.com/problems/min-cost-climbing-stairs/