제4장 귀속과 동태 기획(一)

1, 피보나치 수열 문제의 귀환과 동태 기획 보충 문제 1: 정수 n을 정하고 계단 수를 대표한다. 한 번에 2개 또는 1개의 계단을 뛰어넘을 수 있고 몇 가지 걸음걸이가 있는지 되돌려준다.예를 들어 n=3은 세 번에 한 계단을 건널 수 있다.두 계단을 먼저 건너고 한 계단을 더 건너도 된다.한 계단을 먼저 건너고 두 계단을 더 건너도 된다.그래서 세 가지 방법이 있어요.보충제목2: 암소가 매년 한 마리의 암소를 낳고 영원히 죽지 않는다고 가정한다.첫해에는 성숙한 암소 1마리가 있었고, 이듬해부터는 암소가 소를 낳기 시작했다.암소 한 마리당 3년 후에 익으면 암소를 낳을 수 있다.정수 n을 정하여 n 년 후의 수량을 구하다.예를 들어 n=6, 첫해에 암소 한 마리를 a로 기록한다.이듬해 a는 새 암소를 낳았는데 b로 기록되어 있고 총수는 2이다.3년에 a는 새로운 암소를 낳았는데 c로 기록되었고 총 소 수는 3이다.4년째 a는 새 암소를 낳았는데 d로 기록되어 총 수는 4이다.5년째 b가 성숙했고 a와 b는 각각 새로운 암소를 낳았는데 총수는 6이다.6년째 c도 성숙했다. a, b와 c는 각각 새로운 암소를 낳았고 총수는 9로 9로 되돌아갔다.요구사항: 시간 복잡도 O(logn).원문제의 해답: 폭력의 귀속 해법을 쉽게 쓸 수 있고 시간의 복잡도는 O(2의 n차)이다.코드는 다음과 같습니다.

public static int f1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
}

복잡도 O(n) 방법:

public static int f2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = 1;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
}

이것은 귀속할 필요가 없다. 피보나치 수열은 앞의 두 항목에 근거하여 뒤의 값을 구할 수 있다.방법3: O(logn)시간 복잡도 방법.분석: 행렬 곱셈 방식으로 시간 복잡도를 O(logn)로 낮출 수 있다.f(n)= f(n-1)+f(n-2)는 2단계 추이 수열로 반드시 행렬 곱셈의 형식으로 표시할 수 있고 상태 행렬이 2*2인 행렬(이것은 너무 어려워 잠시 이해할 수 없다).보충문제1: 계단은 1개, 주법은 1개, 두 가지 방법이 있는데 n급이 있으면 마지막에 n급으로 올라가는 경우 n-2급 계단에서 직접 2단계를 올라가거나 n-1급 계단을 올라가기 때문에 계단은 n급 방법이 있다. n-2급 계단으로 올라가는 방법수에 n-1급 계단으로 올라가는 방법수, 즉 s(n)=s(n-1)+s(n-2), 초기항 s(1)=1, s(2)=피치와 유사하다.그러나 서로 다른 것은 초기항이 다르기 때문에 2의 n차방과 O(n)를 쉽게 쓸 수 있는 방법이다. 아래의 s1방법과 s2방법을 보십시오.

public static int s1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return s1(n - 1) + s1(n - 2);

    }

public static int s2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int res = 2;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
}

이상은 2의 n차방과 O(n)의 복잡도 방법이다.다음은 O(logn)의 복잡도를 구하는 방법이자 상태 행렬을 구하고 행렬 곱셈을 사용한다.보충문제2: 모든 소는 죽지 않는다. c(n)=c(n-1)+c(n-3).피보나치 수열과 유사하지만 c(n)항은 c(n-1)와 c(n-3)항의 값에 의존하고 피보나치 수열은 f(n-1)와 f(n-2)항의 값에 의존한다.c1과 c2 방법은 각각 2의 n차방과 O(n) 시간 복잡도의 방법이다.

public static int c1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        return c1(n - 1) + c1(n - 3);
}

public static int c2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        int res = 3;
        int pre = 2;
        int prepre = 1;
        int tmp1 = 0;
        int tmp2 = 0;
        for (int i = 4; i <= n; i++) {
            tmp1 = res;
            tmp2 = pre;
            res = res + prepre;
            pre = tmp1;
            prepre = tmp2;
        }
        return res;
}

2. 행렬의 최소 경로와 제목: 행렬 m을 정하고 왼쪽 상단에서 매번 아래로 내려가거나 오른쪽으로만 갈 수 있으며 마지막으로 오른쪽 하단의 위치에 도달한다. 경로의 모든 숫자를 누적하면 경로와 모든 경로와 중 가장 작은 경로와 되돌아간다.예: 행렬은 다음과 같습니다. 1 3 5 9 8 1 3 4 5 0 6 1 8 4 0 이 행렬은 경로 1, 3, 1, 0, 6, 1, 0 입니다.합은 12입니다. 이것은 가장 작은 경로 합입니다.사고방식: 이것은 고전적인 동적 기획 문제로 가설 행렬의 크기는 m*n, m행 n열이다.선생은 크기가 m와 같은 행렬 dp, dp[i][j]의 값은 왼쪽 상단(즉 (0,0)) 위치에서 (i,j) 위치까지의 최소 경로와m의 첫 줄의 모든 위치에서 (0,0)위치부터 (0,j)위치까지 오른쪽으로만 갈 수 있기 때문에 (0,0)위치에서 (0,j)위치까지의 경로와 m[0][0.j]의 누적 결과입니다.같은 이치로 m의 첫 번째 열의 모든 위치, 즉 (i, 0)(0<=i<=m), (0, 0)위치에서 (i, 0)위치까지는 아래로 갈 수 밖에 없기 때문에 (0, 0)위치에서 (i, 0)위치까지의 경로와 m[0.i][0]가 누적된 결과이다.제목의 예를 들어 dp의 첫 번째 줄과 첫 번째 열의 값은 다음과 같다. 14 9 18 9 14 22가 생성한 dp는 다음과 같다. 1 4 9 18 9 5 8 12 14 5 11 12 12 13 15 12 사고방식: 첫 번째 줄과 첫 번째 열을 제외하고 모든 위치는 왼쪽에서 자신의 경로와 더 작은지 위에서 자신의 경로와 더 작은지를 고려한다. 가장 오른쪽 하단의 값이 바로 전체 문제의 답이다.구체적인 절차는 아래 코드의 minPathSun1 방법을 참조하십시오.

public static int minPathSum1(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
}

매트릭스에는 m*n의 위치가 있는데 각 위치는 (0,0)위치에서 자신의 최소 경로와 계산할 때 위쪽 위치의 최소 경로와 왼쪽 위치의 최소 경로와 어느 것이 더 작은지 비교할 뿐이다. 그래서 시간 복잡도는 O(m*n)이고 dp 매트릭스의 크기는 m*n이기 때문에 추가 공간 복잡도는 O(m*n)이다.동적 기획이 공간을 압축한 후의 방법, 이 문제의 고전적인 동적 기획 방법은 공간을 압축한 후에도 시간 복잡도는 여전히 O(m*n)이지만 추가 공간 복잡도는 O(m*n)에서 O(min{m, n})로 낮출 수 있다. 즉, 크기가 m*n인 dp 행렬을 사용하지 않고 크기가min{m, n}인arr수조만 사용한다.구체적인 과정은 다음과 같다. 1) 길이가 4인 수조arr를 생성하는데 초기에arr={0,0,0,0}, 우리는 (0,0)위치에서 m의 첫 줄에 이르는 모든 위치, 최소 경로와 (0,0)위치의 값부터 순서대로 누적된 결과를 알고 있기 때문에 순서대로arr={1,4,9,18}로 설정한다. 이때arr[j]의 값은 (0,0)위치에서 (0,j)위치까지의 최소 경로와2), 1단계에서arr[j]

public static int minPathSum2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int more = Math.max(m.length, m[0].length);
        int less = Math.min(m.length, m[0].length); // 
        boolean rowmore = more == m.length; // 
        int[] arr = new int[less]; 
        arr[0] = m[0][0];
        for (int i = 1; i < less; i++) {
            arr[i] = arr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
        }
        for (int i = 1; i < more; i++) {
            arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
            for (int j = 1; j < less; j++) {
                arr[j] = Math.min(arr[j - 1], arr[j])
                        + (rowmore ? m[i][j] : m[j][i]);
            }
        }

        return arr[less - 1];

}

확장: 본체가 공간을 압축하는 방법은 거의 모든 2차원 동적 기획표를 필요로 하는 제목에 적용될 수 있고 하나의 그룹을 통해 갱신하는 방식으로 대량의 공간을 절약할 수 있다.최적화되기 전에 특정한 위치의 동적 계획을 얻는 가치 있는 과정은 행렬에서 두 번의 주소 찾기를 하는 것이다. 최적화된 후에 이 과정은 한 번의 주소 찾기만 하면 프로그램의 상수 시간도 어느 정도 가속화된다.그러나 공간 압축 방법은 한계가 있다. 본체가'프린트가 최소 경로와 경로를 가진'것으로 바꾸면 공간 압축 방법을 사용할 수 없다.만약에 본 문제와 같은 2차원 표가 필요한 동적 기획 문제가 있다면 최종 목적은 가장 우수한 구체적인 경로를 찾으려는 것이고 종종 완전한 동적 기획표가 필요하지만 가장 좋은 값만 찾으려면 공간 압축 방법을 사용할 수 있다.공간 압축 방법은 스크롤 업데이트이기 때문에 이전에 구해한 값을 덮어쓰고 구해 궤적을 거슬러 올라갈 수 없게 합니다.3, 환전의 최소 화폐 수 제목: 주어진 수조arr,arr의 모든 값은 정수이며 중복되지 않습니다.모든 값은 하나의 액면가의 화폐를 대표하고 모든 액면가의 화폐는 임의의 장을 사용할 수 있다. 그리고 정수를 정해서 aim가 찾는 돈의 수를 대표하고 aim를 구성하는 최소 화폐의 수를 구한다.예:arr={5,2,3},aim=20.4장 5원으로 20원을 구성할 수 있고 다른 거스름돈은 더 많은 화폐를 사용해야 하기 때문에 4로 돌아간다.arr={5,2,3},aim=0. 어떤 화폐도 쓰지 않아도 0위안을 구성할 수 있기 때문에 0으로 되돌아간다.arr={3,5},aim=2. 2원을 만들 수도 없고, 돈을 거슬러 줄 수도 없는 상황에서 기본적으로 -1을 되돌려준다.보충 제목: 주어진 그룹arr,arr의 모든 값은 정수입니다.매 값은 단지 한 장의 돈의 액면가를 대표할 뿐이다. 그리고 정수를 정해서 aim가 찾으려는 돈의 수를 표시하고 aim를 구성하는 최소 화폐의 수를 구한다.예:arr={5,2,3},aim=20.5, 2, 3원짜리 돈이 한 장씩 있어서 20원을 만들 수 없어 -1로 되돌아간다.arr={5,2,5,3},aim=10. 5원짜리 화폐는 두 장으로 10원을 구성할 수 있기 때문에 2로 되돌아간다.arr={5,2,5,3},aim=15. 모든 화폐를 합치면 15위안이 되어 4위안으로 돌아간다.arr={5,2,5,3},aim=0. 어떤 화폐도 쓰지 않아도 0위안을 구성하여 0으로 되돌아갈 수 있다.해답: 원문제의 고전적인 동태적 기획 방법.만약arr의 길이가 n이면 길이가 n이고 열수가aim+1인 동적 기획표의 dp를 생성합니다.pp[i][j]의 의미는arr[0.i] 화폐를 임의로 사용할 수 있는 상황에서 j가 필요로 하는 최소 장수를 구성하는 것이다.이 정의에 따라 dp[i][j]의 값은 다음과 같은 방식으로 계산된다. 1) dp[0..1][0]의 값(즉 dp 행렬에서 첫 번째 열의 값)은 거스름돈이 0일 때 필요한 최소 장수를 표시하고 돈이 0일 때 아무런 화폐도 필요하지 않기 때문에 모두 0으로 설정한다.2), dp[0][0.aim]의 값(dp 행렬 첫 줄의 값)은 arr[0] 화폐만 사용할 수 있는 상황에서 어떤 돈의 최소 장수를 찾는 것을 나타낸다.예를 들어arr[0]=2를 찾으면 찾을 수 있는 돈은 2, 4, 6, 8이다. 그래서 dp[0][2]=1, dp[0][4]=2, dp[0][6]=3을 찾을 수 없게 한다. 첫 번째 줄의 다른 위치가 대표하는 돈은 일률적으로 찾을 수 없기 때문에 일률적으로 32자리 정수의 최대치로 설정하고 우리는 이 값을 max로 기록한다.3) 나머지 위치는 왼쪽에서 오른쪽, 위에서 아래로 계산한다.가령 위치(i, j)를 계산했다면 dp[i][j]의 값은 아래의 상황에서 나올 수 있다. a, 현재 화폐arr[i]의 최소 장수, 즉 dp[i-1][j]의 값을 전혀 사용하지 않는다.b, 현재 화폐arr[i]의 최소 장수, 즉 dp[i-1][j-arr[i]]+1만 사용합니다.c, 현재 화폐arr[i] 두 장의 최소 장수, 즉 dp[i-1][j-2*arr[i]+2만 사용한다.d, 현재 화폐arr[i]의 최소 장수, 즉 dp[i-1][j-3*arr[i]]+3만 사용.모든 경우, 최종적으로 가장 적은 수를 취한다.그래서: dp[i] [j] [j] = min {dp[i - 1] [j-k*arr[i] + k (0 <=k)} ====min {dp[i - 1] [j-k*arr[i] + k (0 <=k)} ======< dp[i] [i] [i-1] [j], min {dp[i - 1] [j-x arr [i] [j-]++++++ k [i]++ + k ========[j] ========min dp[i - 1] [i- 1] [j] [j] [j] [j] [j], min - 1] [j], min - [j] [j] [{dp[i-1][j-arr[i]-y*arr[i]+y(0<=y)}=>dp[i][j-arr[i]]]]가 있기 때문에 최종적으로 dp[i][j]=min{dp[i-1][j], dp[i][j][j][j][j][j]][j]][j]]][j]]]],만약에 j-arr[i]<0, 즉 경계를 넘었다면 이것은 arr[i]가 너무 작아서 한 장으로 모두 돈의 j를 초과할 수 있다는 것을 의미한다. dp[i][j]=dp[i-1][j]를 사용하면 된다.구체적인 과정은 아래 코드의minCoins 방법을 참고하면 전체 과정의 시간 복잡도와 추가 공간 복잡도는 모두 O(n*aim)이고 n은arr의 길이이다.

public static int minCoins1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][aim + 1];
        for (int j = 1; j <= aim; j++) {
            dp[0][j] = max;
            if (j - arr[0] >= 0 && dp[0][j - arr[0]] != max) {
                dp[0][j] = dp[0][j - arr[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                left = max;
                if (j - arr[i] >= 0 && dp[i][j - arr[i]] != max) {
                    left = dp[i][j - arr[i]] + 1;
                }
                dp[i][j] = Math.min(left, dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
}

원문제는 동적 기획을 바탕으로 하는 공간 압축 방법이다.참고 행렬의 최소 경로와 문제, 즉 위 문제.