Leetcode #70: Climbing Stairs
class Solution { | |
public: | |
int climbStairs(int n) { | |
vector<int> dp(n+1); | |
dp[1] = 1; | |
dp[2] = 2; | |
for (int i=3; i<=n; i++) { | |
dp[i] = dp[i-1] + dp[i-2]; | |
} | |
return dp[n]; | |
} | |
}; | |
// Note: Space complexity of this solution can be reduced to O(1) by using 2-3 variables instead of an array/vector. | |
// As this generates a Fibonacci series, you can use a relatively more complex but efficient way of finding Nth Fibonacci number instead of using the dynamic programming approach. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment