동적 프로그래밍의 기본 아이디어는 문제를 여러 하위 프로젝트로 해결하고 먼저 하위 문제를 해결하고 이러한 하위 문제의 솔루션을 저장하는 것입니다. 더 큰 하위 프로젝트를 해결할 때 미래에 이러한 하위 문제의 솔루션을 사용해야하는 경우,이 계산 된 솔루션을 직접 추출하여 반복적 인 작업을 피할 수 있습니다. 하위 문제를 저장하는 솔루션은 배열에서 저장과 같은 양식 방법을 사용하여 채울 수 있습니다.
실용적인 예를 사용하여 동적 프로그래밍의 알고리즘 아이디어 - 동전 변화의 문제를 반영하십시오.
질문 설명 :
동전이 여러 개 있고 무제한이 있다고 가정하십시오. 특정 수의 변화를 구성 할 수있는 최소 동전 수를 찾으십시오. 예를 들어, 여러 유형의 동전은 [1, 3, 5], 액면가가 2 (1, 1)의 최소 동전 수, 액면가가 4 인 최소 동전 수는 2 (1, 3)이고 액면가를 가진 최소 동전 수는 3 (5, 5, 1 또는 5, 3, 3)입니다.
문제 분석 :
다른 동전 세트가 배열 동전 [0, ..., n-1]이라고 가정하십시오. 그런 다음 액면가 k를 사용하여 최소 코인 수를 찾은 다음 카운트 함수 및 동전 배열 동전 이이 조건을 충족합니다.
count (k) = min (count (k -coin [0]), ..., count (k -coin [n -1]) + 1;
그리고 이전 공식은 조건 k -coin [i]> = 0 && k -coin [i] <k가 충족되는 경우에만 유지됩니다.
k-coin [i] <k, count (k)를 계산할 때 count (i) (i) (i <- [0, k-1])를 충족해야하므로 여기에는 역 추적 문제가 포함됩니다.
따라서 매트릭스 매트릭스 [k + 1] [coin.length + 1]를 만들 수 있으므로 매트릭스 [0] [j]가 모두 0 값으로 초기화되고 매트릭스 [i] [Coin.Length]에서 I의 액면가가있는 최소 코인 수를 저장합니다.
특정 프로세스는 다음과 같습니다.
* K | 동전 1 3 5 분 * 0 0 0 0 0 0 0 0 0 0 0 0 1 * 2 2 * 3 3 3 3 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2 * ...
마지막으로, 특정 Java 코드 구현은 다음과 같습니다.
public static int backtrackingcoin (int [] coins, int k) {// backtracking method + dynamic programming if (coins == null || coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [Coins.length + 1]; for (int i = 1; i <= k; i ++) {for (int j = 0; j <coins.length; j ++) {int prek = i- 코인 [j]; if (prek> -1) {// 0 이상인 경우에만 배열 매트릭스에 prek가 존재할 수 있으며 백 트랙을 수행 할 수 있습니다. 매트릭스 [i] [j] = matrix [prek] [coins.length] + 1; // 액면가 I는 if (matrix [i] [coins.length] == 0 || matrix [j] <matrix [j] <matrix [coins.length]) {// Coins의 현재 숫자가 최소 인 경우, COINS의 최소한을 업데이트합니다. 매트릭스 [i] [coins.length] = 행렬 [i] [j]; }}} return matrix [k] [coins.length]; }코드가 테스트되었으며 질문에 의해 주어진 모든 테스트 사례가 통과되었습니다!
요약
위는 Java Dynamic Programming의 코인 변경 문제 구현 코드에 대한이 기사의 전체 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!