Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public int climbStairs(int n) {
- if(n==0 || n==1 || n==2) {
- return n;
- }
- int[] cache = new int[n+1];
- for(int i=0; i<=2; i++) {
- cache[i] = i;
- }
- for(int i=3; i<=n; i++) {
- cache[i] = -1;
- }
- return climb(n, cache)[n];
- }
- private int[] climb(int n, int[] cache) {
- int steps = 0;
- if(n-1 >= 0) {
- if(cache[n-1] >= 0) {
- steps += cache[n-1];
- } else {
- cache = climb(n - 1, cache);
- steps += cache[n-1]; // climbing one step
- }
- }
- if(n-2 >= 0) {
- if(cache[n-2] >= 0) {
- steps += cache[n-2];
- } else {
- cache = climb(n - 2, cache);
- steps += cache[n-2]; // climbing two steps
- }
- }
- cache[n] = steps;
- return cache;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement