Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #746: Min Cost Climbing Stairs
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
if (n == 0) {
return 0;
}
if (n == 1) {
return cost[0];
}
vector<int> dp(n);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i=2; i<n; i++) {
dp[i] = cost[i]+min(dp[i-1], dp[i-2]);
}
return min(dp[n-1], dp[n-2]);
}
};
// Note: Space complexity of this solution can be reduced to O(1) by using 3-4 variables instead of an array/vector.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.