[leetcode] 1137. N-th Tribonacci Number, 62. Unique Paths

링크

 

DP(Dynamic Programming)

하나의 큰 문제를 작은 문제로 나누어 해결하는 기법

 

동적프로그래밍을 사용하는 대표적인 문제가 피보나치 수열이다.

f(n) = f(n - 1) + f(n - 2) (n > 2), f(0) = 0, f(1) = 1

 

위의 수열을 해결하기 위해 재귀적으로 문제를 해결할 수도 있지만 중복 실행이 발생하게 되고 n이 커지면 커질수록 비효율적이다.

따라서 f(0), f(1)을 배열에 저장해서 한번 구한 값을 또 구하지 않도록 아래와 같이 f(n)을 구할 때까지 반복적으로 연산을 진행한다.

 

 

DP를 사용해서 문제를 풀기 위해서는 문제를 작은 문제로 나누고 이 결과를 이용해서 동일한 작은 문제를 해결하도록 해서 소문제를 재사용해야한다.

즉, 비슷한 여러 개의 소문제로 나눌 수 있어야하며, 소문제의 결과가 다른 소문제를 푸는 열쇠로 작용할 수 있어야한다.

class Solution {
    public int tribonacci(int n) {
        int[] arr = new int[n + 3];

        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;

        if (n > 2) {
            for(int i = 3; i <= n; i++) {
                arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];
            }
        }
        
        return arr[n];
    }
}

 

 

Unique Paths

 

top-left에서 down-right에 있는 로봇을 만나러 가야하는데 경로가 몇 개가 있는지에 대한 문제

down과 left만을 반복하고 있고 가고자 하는 위치까지의 도달 경로 개수 = 이전 위치까지의 도달 경로 개수 합(위 + 왼쪽 경로 개수)

 

초기값은 오른쪽으로만 갔을 경우, 아래로만 갔을 경우 각 경로는 1개라고 세팅했다.

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] grid = new int[m][n];

        // 초기값 세팅
        for(int i = 0; i < m; i++) {
            grid[i][0] = 1;
        }
        for(int i = 0; i < n; i++) {
            grid[0][i] = 1;
        }

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
            }
        }

        return grid[m - 1][n - 1];
    }
}