70. Climbing Stairs

# Easy

DP + record

total(n) = total(n-1) + total(n-2)

total(n) means how many climb ways for n stairs.

Java(super easy)

class Solution {
    public int climbStairs(int n) {
        int[] steps = new int[n+1];
        steps[0] = 1;
        steps[1] = 1;
        if(n == 1) return steps[1];
        
        for(int i = 2; i <= n; i ++) {
            steps[i] = steps[i-1] + steps[i-2];
        }
        return steps[n];
    }
}

Python

class Solution:
    def climbStairs(self, n: int) -> int:
        sumPath = [-1]*(n+1)
        return self.dfs(n, sumPath)
        
        
    def dfs(self, n, sumPath):
        # edge case
        if n == 0:
            sumPath[n] = 0
            return 0
        elif n == 1:
            sumPath[n] = 1
            return 1
        elif n == 2:
            sumPath[n] = 2
            return 2
        
        # regular case
        if sumPath[n] == -1:
            sumPath[n] = self.dfs(n-1, sumPath) + self.dfs(n-2, sumPath)
        return sumPath[n]