Leetcode 70: Climbing Stairs

The below is a very famous DP problem.

You are climbing a staircase that has n steps. You can take the steps either 1 or 2 at a time. Calculate how many distinct ways you can climb to the top of the staircase.

Example: for n=1, output = 1

for n=2, output = 2

for n=4, output = 5

Below is the Java code for the problem with O(n) time complexity and O(n) space complexity.

int solution(int n) {
    // Dp array to store the value for n cases
    int dp[] = new int[n+1];
    // base cases, if no stairs - 1 way, if 1 stair - 1 way
    dp[0] = 1;
    dp[1] = 1;

    // for climbing nth stair, we can either come from n-1th or n-2th
    for(int i=2; i<n+1; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}