Leetcode - 70. Climbing Stairs

문제

계단을 한칸 혹은 두칸씩 오를 수 있다고 할때, n번째 계단을 오르는 경우의 수는?

https://leetcode.com/problems/climbing-stairs/

유사문제

• 746. Min Cost Climbing Stairs
  계단을 오르는 최소비용값 이라는 차이가 있음.

해결 O(N)

이런 문제는 base case값만 잘 생각해서 리턴하면 최종값은 자동으로 계산됨. dp의 memoization을 사용하면 O(N)에 해결.
헉 다풀고 보니 풀이가 피보나치 수열과 동일하다.

1. constraints
 - 1 <= n <= 45
2. Ideas
 - DP 
   - dp[] = how many way
   - dp[n] = dp[n-1] + dp[n-2] (dp[1] == 1, dp[2] == 2)
3. Test cases
 - assert(recur(1) = 1)
 - assert(recur(2) = 2)
 - assert(recur(3) = 3)
 - assert(recur(4) = 5)

int dp[46];
int climbStairs(int n){
    if (dp[n])
        return dp[n];
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    dp[n] = climbStairs(n - 1) +  climbStairs(n - 2);
    return dp[n];
}

해결 FP 스타일 꼬리재귀

230801 작성

함수형 프로그래밍 Scala에서는 아래와 같이 꼬리재귀로 loop를 작성한다. 컴파일러가 이경우 내부적으로 while로 컴파일하여 스택오버플로우를 방지할수 있다. 꼬리재귀는 재귀함수의 마지막 부분이 재귀함수 자신만 리턴하는 형식을 말한다. 아래의 코드도 go()를 리턴하는것 외에는 아무것도 하지 않는다. 그런데 만약 go(n-1) + go (n-2) 형식이나 go(n-1) * n 등의 형식을 리턴한다면 꼬리재귀가 아니다.

object Solution {
    def climbStairs(n: Int): Int = {
        def go(n: Int, prev: Int, curr: Int): Int = {
            if (n <= 1) prev
            else go(n - 1, curr, prev + curr)
        }
        go(n, 1, 2)
    }
}

아래 두 종류의 꼬리재귀 형식을 기억하자.

피보나치 수열

object Solution {
    def fib(n: Int): Int = {
        def go(n: Int, prev: Int, curr: Int): Int = {
            if (n <= 0) prev
            else go(n - 1, curr, prev + curr)
        }
        go(n, 1, 2)
    }
}
/*
Fibonacci Number
0 1 1 2 3 5
f(6)
  go(6, 0, 1)
    go(5, 1, 0+1)
      go(4, 1, 1+1)
        go(3, 2, 1+2)
          go(2, 3, 2+3)
            go(1, 5, 3+5)
*

Factorial

object Solution {
    def fac(n: Int): Int = {
		def go(n: Int, acc: Int): Int = {
        	if (n <= 0) acc
            else go(n - 1, acc * n)
        }
        go(n, 1)
	}
}
/*
fac(5)
  go(5, 1)
    go(4, 1*5)
      go(3, 1*5*4)
        go(2, 1*5*4*3)
          go(1, 1*5*4*3*2)
            

*/