70. Climbing Stairs
# Easy
DP + record
total(n) = total(n-1) + total(n-2)
total(n) means how many climb ways for n stairs.
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];
}
}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]Last updated
Was this helpful?