climbing stairs

climbing stairs

Easy problem like Fibonacci, const space complexity solution.
 1 class Solution {
 2 public:
 3     int climbStairs(int n) {
 4         int dp[3];
 5         dp[0] = 1;
 6         dp[1] = 2;
 7         for ( int i = 2; i < n; i++ ) {
 8             dp[i%3] = dp[(i-1)%3]+dp[(i-2)%3];
 9         }
10         return dp[(n-1)%3];
11     }
12 };

Loading Disqus comments...
Table of Contents