O(n) time complexity and O(n) space complexity and 0ms solution


  • 0
    A
    class Solution {
    public:
        int climbStairs(int n) {
            if(n==1) return 1;
            if(n==2) return 2;
            int count[n+1];
            count[0]=0;
            count[1]=1;
            count[2]=2;
            for(int i=3;i<=n;i++)
                count[i]=count[i-1]+count[i-2];
            return count[n];
        }
    };

  • 0
    A

    You could have made it O(1) by just considering two values
    int dp[2];

    and updating them in the loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.