Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Naive Way: A DP approach should be able to conquer this problem. The basic logic is
opt[i] // # of distinct ways to reach top
// base case
opt[0] = 1, opt[1] = 1 (edge case should be n=0, return 0)
// iteration
opt[i] = opt[i-1]+opt[i-2]
public class Solution {
public int climbStairs(int n) {
// DP
// edge case
if(n == 0) return 0;
int opt[] = new int[n+1];
// base case
opt[0] = 1;
opt[1] = 1;
// iteration
for(int i = 2;i <= n;i++) opt[i] = opt[i-1]+opt[i-2];
return opt[n];
}
}
It turns out this follows Fibonacci Sequence. So there is a famous DFS recursive method. Could use path memorizing to reduce time complexity from O(2^n) to O(n).
public class Solution {
public int climbStairs(int n) {
// DFS
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,1);
map.put(1,1);
return dfs(n, map);
}
private int dfs(int n, Map<Integer, Integer> map){
// fast ending
if(map.containsKey(n)) return map.get(n);
// recursion
int rslt = dfs(n-1, map) + dfs(n-2, map);
map.put(n, rslt);
return rslt;
}
}
No comments:
Post a Comment