Easy to understand C# AC (with explanation)


  • 0
    P

    The number of ways of reaching the last step from the previously taken step would be from either (n-1)th step or (n-2)th step. So the total number of ways of reaching the top would be the sum of number of ways of reaching (n-1) and (n-2)th step.
    So the recursive version of this would be:

    public int ClimbStairs(int n) {
            if(n<0)
               return 0;      \\base case
            else if(n == 0)
               return 1;
            return ClimbStairs(n-1) + ClimbStairs(n-2);
    }
    

    Converting it into a DP solution:

        public int ClimbStairs(int n) {
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i=2;i<=n;i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    

Log in to reply
 

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