동적 프로그래밍 01에 대한 무차별 대입 재귀

주제 1

행에 N개의 위치가 있고 1~N으로 표시되고 N은 2보다 크거나 같아야 한다고 가정합니다.
로봇은 처음 행의 M 위치에 있습니다(M은 1~N 중 하나여야 함).
로봇이 위치 1에 도달하면 다음 단계는 오른쪽의 위치 2로만 이동할 수 있습니다.
로봇이 N 위치에 도달하면 다음 단계는 왼쪽 N-1 위치까지만 이동할 수 있습니다.
로봇이 중간 위치에 오면 다음 단계는 왼쪽 또는 오른쪽으로 이동할 수 있습니다.
로봇이 K 단계를 거쳐 마침내 P 위치(P도 1~N 중 하나임)에 도달해야 한다고 지정하는 방법은 몇 가지입니까?
4개의 매개변수 N, M, K, P가 주어지면 메서드의 수를 반환합니다.

솔루션 #1 무차별 대입 재귀

기본 사례: K가 0이고 로봇의 현재 위치가 P 위치인 경우에만 한 가지 방법을 찾습니다.

경계 조건: 로봇 현재 위치가 1일 때. 다음 단계는 오른쪽으로만 갈 수 있습니다. 로봇 현재 위치가 N일 때. 다음 단계는 왼쪽으로만 갈 수 있습니다.

중간 위치: 로봇이 중간 위치에 있을 때. 다음 단계는 왼쪽 또는 오른쪽으로 이동할 수 있습니다.

public static int myWays1(int N, int M, int P, int K) {
        return myProcess1(M, K, P, N);
    }
// cur: robot current position
// rest: remaining steps
// aim: target position
// N: position of 1~N
    public static int myProcess1(int cur, int rest, int aim, int N) {
        if (rest == 0) { // no steps 
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) { // current position is 1,go to right
            return myProcess1(cur + 1, rest - 1, aim, N);
        }
        if (cur == N) { // current position is N, go to left 
            return myProcess1(N - 1, rest - 1, aim, N);
        }
        // current position in any middle position, go to left or right
        return myProcess1(cur + 1, rest - 1, aim, N) + myProcess1(cur - 1, rest - 1, aim, N);
    }

Solution #2 메모라이즈 검색

솔루션 #1에서 cur 및 rest 매개변수만 변경되는 것을 확인할 수 있습니다. Solution #1에서 반복 계산하는 과정이 있음을 그림에서 알 수 있다. 따라서 캐시를 사용하여 이미 계산된 값을 넣을 수 있습니다.

public static int myWays2(int N, int start, int aim, int K) {
        // dp cache
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return myProcess2(start, K, aim, N, dp);
    }

    public static int myProcess2(int cur, int rest, int aim, int N, int[][] dp) {

        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = myProcess2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp) + myProcess2(cur - 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

솔루션 #3 동적 프로그래밍

N+1 * K+1 2차원 배열을 준비합니다. 행은 위치를 나타내고 열은 나머지 단계를 나타냅니다.

남은 단계가 0이고 위치가 P일 때 기본 사례를 찾으므로 dp[P][0] = 1로 설정합니다.

첫 번째 행은 다음 행의 [rest - 1] 위치에 따라 달라집니다.
마지막 행은 이전 행의 [rest - 1] 위치에 따라 달라집니다.
중간 행은 이전 행과 다음 행의 [rest - 1] 위치의 합에 따라 달라집니다.

반환 결과는 dp[M][K]입니다.

    public static int myWays3(int N, int M, int P, int K) {
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;

        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }

        return dp[M][K];
    }