Climbing Stairs || C++ solution with O(1) space and O(n) time
Climbing Stairs You have to climb n steps on a stair, each time you can either climb 1 step or 2 steps. You have to return the number of ways you can climb. Example Input: n = 2 Output: 2 Explanation: There are two ways to climb to reach the top. 1. 1 step + 1 step = 2 2. 2 steps = 2 Approach 1: we will use dynamic programming to solve. use a top-down( recursion and memorization) approach here. Time Complexity: O(n) for going from n to 0 Space Complexity: O(n) for recursion stack O(n) for dp array Code: int climbStairs ( int n ) { int ans = 0 ; int i = n ; vector < int > dp ( n + 2 , 0 ) ; ans = climb ( i , v ) ; return ans ; } int climb ( int i , vector < int > & dp ) { if ( i < 0 ) return 0 ; if ( i == 0 ) { return 1 ; } if ( dp [ i ] != 0 ) return dp [ i ] ; return dp [ i ] = climb ( i - 1 , dp ) + climb ( i - 2 ,...