Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

• Input: n = 2
• Output: 2
• Explanation: 1 step + 1 step, 2 steps

Example 2:

• Input: n = 3
• Output: 3
• Explanation: 1 step + 1 step + 1 step, 1 step + 2 steps, 2 steps + 1 step

class Solution {
 
    public int climbStairs(int n) {
        var dp = new int[n + 1];
        return helper(n, dp);
    }

    private int helper(int n, int[] dp) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }   
        if (dp[n] != 0) {
            return dp[n];
        }
        dp[n] = helper(n - 1, dp) + helper(n - 2, dp);
        return dp[n];
    }

}