Leetcode 70) Climbing Stairs

29 Jul 2021 in Algorithms

답안1) Fibonacci number

• 재귀적으로 뒤에서 부터 콜

class Solution {
    public int climbStairs(int n) {
        int[] res = recursive(n);
        return res[0];    
    }
    public int[] recursive(int n){
        if(n==1){
            int[] array = {1,1};
            return array;
        }

        int[] ans = recursive(n-1);
        int res = ans[0] + ans[1];
        int[] array = {res,ans[0]};
        return array;
    }
}

답안2) Dynamic programming

• 앞에서 부터
• 답안1보다 이게 더 쉽다. 앞에서 부터 뭘 더해야할 때, 이런식으로!

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

오답

• 오 좋은 오답!

  • 이렇게 했더니 time limit 뜸.
  • climbStairs(n-1) 이부분,반복될 수 있는 부분이다. 근데 계속 매번 새로 돌아가서 ..

  class Solution {
      public int climbStairs(int n) {
          if(n==1){
              return 1;
          }
          if(n==0){
              return 1;
          }
            
          int res = climbStairs(n-1) + climbStairs(n-2);
          return res;    
      }
  }
  

• time limit 떴다. (40까지는 결과가 나오는데 41부터 time limit 뜸.)

• 굳이 백트래킹 알고리즘을 사용할 필요가 없나부다.

  class Solution {
      int res = 0;
      public int climbStairs(int n) {
          helper(n);
          return res;    
      }
    
      public void helper(int n){
          if(n==0){
              res++;
              return;}
          if(n<0){
              return;
          }
          for(int i=1;i<3;i++){
              helper(n-i);
          }
      }
  }