Constant space DP


  • 0
    J

    The idea is the same. But instead of using the array to store the dp, we notice that dp[i] = dp[i-2] + dp[i-1] (optimial sub-structure relation), meaning the value at n only depends on the previous two values. So we can create a constant-space array of size two and specifying the index using %.

    public class Solution {
        public int climbStairs(int n) {
            //initialize
            int[] dp = new int[2]; 
            dp[0] = 1;
            dp[1] = 1;
            
            //run dp
            for (int i=2; i<n+1; i++) {
                dp[i%2] = dp[(i-1)%2] + dp[(i-2)%2];
            }
            
            return dp[n%2];
        }
    }
    

Log in to reply
 

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