leetcode -- Climbing Stairs

4235 단어 LeetCode
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
large data TLE
역귀해법의 시간 복잡도는 O(2^lgn)이기 때문에 n이 점점 커질 때 계산 중복해로 인해 시간 복잡도는 지수급으로 증가한다
 1 public int climbStairs(int n) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         if(n <= 0){
 5             return 0;
 6         }
 7         if(n == 1){
 8             return 1;
 9         }
10         if(n == 2){
11             return 2;
12         }
13         
14         return climbStairs(n-1) + climbStairs(n-2);
15     }

bottom up
시간 복잡도: O(n)
 1 public int climbStairs(int n) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         int[] data = new int[n + 1];
 5         data[0] = 0;
 6         data[1] = 1;
 7         if(n >= 2){
 8             data[2] = 2;
 9         }
10         for(int i = 3; i <= n; i++){
11             data[i] = data[i-1] + data[i-2];
12         }
13         return data[n];        
14     }

좋은 웹페이지 즐겨찾기