변경 동전 구현 문제

DP를 사용하여이 고전적인 문제를 해결할 때 구현 문제가 발생했습니다. 문제는 동전 세트가 주어지며 변경 방법의 수를 반환합니다.변경 동전 구현 문제

민주당 방정식은 다음과 같은 것이다 : DP [I] + = DP [I - 경화 [J] DP가 [I] I에 대한 변경을 수행하는 방법의 수를 의미
. , INT 코인 [] = {1, 5} 변화 = 6

make_change_wrong (동전 2

int make_change_wrong(int coin[], int size, int change) { 
    vector<int> DP(change + 1, 0); 
    DP[0] = 1; 

    for (int i = 1; i <= change; ++i) { 
     for (int j = 0; j < size; ++j) { 
      if (i - coin[j] >= 0) { 
       DP[i] += DP[i - coin[j]]; 
      } 
     } 
    } 

    return DP[change]; 
}

주어진 입력 :

여기서 간단 잘못 구현이며 6)은 3을 반환하지만 2는 정확합니다. 그들은 같은 일이있어,

int make_change(int coin[], int size, int change) { 
    vector<int> DP(change + 1, 0); 
    DP[0] = 1; 

    for (int i = 0; i < size; ++i) { 
     for (int j = coin[i]; j <= change; ++j) { 
      DP[j] += DP[j - coin[i]]; 
     } 
    } 

    return DP[change]; 
}

이

나 때문에 나에게 많이 의아해 ... : 같은 논리를 사용

는

, 나는 덜 직관적 인 방법으로 그것을 쓰기 다시하고 정확한 답변을 얻을 누군가 두 가지 구현의 문제에 대해 약간 설명 할 수 있습니까?

출처

2013-07-05 galactica

두 가지 구현간에 서로 다른 대답을 얻는다면 명확하게 동일하지 않습니다.아마도 DP 배열의 내용을 출력 할 때 일부 디버깅 문을 삽입 할 수 있습니다. 이것은 그들이 어떻게 다른지 설명하는 데 도움이 될 수 있습니다. –

Brian, 첫 번째 함수는 {1,1,1,1,1}을 두 번 계산합니다. 두 번째 계산이 올바르게 계산되는 이유를 알지 못했습니다. 두 가지 방법으로 만 코딩됩니다. – galactica

첫 번째 알고리즘이 잘못되었습니다.

DP [5] = 2 {1,1,1,1,1}, {5}

DP [6] DP [5] + DP [1] = 3

을하면 {5,1}이 두 번 세고 있습니다. 편집을 할 그래서이 작업을 수행하는 표준 트릭은 범위 [동전을 사용하여 난 양의 변화를 만드는 방법의 수를 의미하는 당신이

DP[i,m] = DP[i-coin[m],m] + DP[i,m-1]

를 사용할 수있는 교단의 수를 유지하는 것입니다 1.m]. 이것은 분명히 m 번째 교단을 사용하거나 그렇지 않은 경우입니다.

사용중인 두 번째 알고리즘은 동일한 트릭을 수행하지만 실제로 그렇게하는 영리한 방법이며, i 번째 동전을 가져 와서 사용하는 모든 변경 사항을 확인하십시오. 이렇게하면 {1,5} 및 {5,1}과 같은 일을하지 않으므로 계산 초과를 피할 수 있습니다.

출처

2013-07-05 05:08:36 sukunrt

감사합니다 sukunrt, 내 첫 번째 함수가이 입력을 잘못 이해하고 그것을 {1,1,1,1,1} 두 번 계산합니다. 나는 왜 똑같은 생각을 사용하는 코딩이 다른 행동을 생성하는지 볼 수 없다. – galactica

이 문제는 인터뷰 준비 도서 코딩 인터뷰 크래킹이며이 책에 제공된 해결 방법은 전혀 최적화되지 않았습니다. 재귀 (DP없이)를 사용하여 하위 문제를 반복적으로 계산하므로 O (N^3)로 실행됩니다. 동적 프로그래밍 장의 일부이기 때문에 특히 아이러니합니다.

DP를 사용하며 O (N) 시간 동안 실행되는 매우 간단한 작업 솔루션 (Java)입니다.

static int numCombos(int n) { 
    int[] dyn = new int[n + 1]; 
    Arrays.fill(dyn, 0); 
    dyn[0] = 1; 
    for (int i = 1; i <= n; i++) dyn[i] += dyn[i - 1]; 
    for (int i = 5; i <= n; i++) dyn[i] += dyn[i - 5]; 
    for (int i = 10; i <= n; i++) dyn[i] += dyn[i - 10]; 
    for (int i = 25; i <= n; i++) dyn[i] += dyn[i - 25]; 
    return dyn[n]; 
}

출처

2013-07-26 04:16:34 The111

CCI 서적 The111에 대한 좋은 관찰! 많은 문제들에 대해, 나는 제공된 해결책이 "깔끔"하지 않다고 생각한다. 코드는 두 번째 시도와 동일하게 필수적입니다. DP에 관한 한 가지는 재귀 방정식을 성공적으로 얻었더라도 올바르게 구현하는 것이 여전히 까다 롭습니다. – galactica

두 번째 방법에 대한 귀하의 의견을 시도하십시오 :

coin[5] = {1,5,10,20,30}; 
make_change(coin,5,30);

이 (21) 내 테스트 케이스를 확인하시기 바랍니다 반환합니다.

출처

2013-10-21 12:40:35 Mahfuz

변경 동전 구현 문제

답변

관련 문제