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