algorithm - 동적 문제 질문에서 겹치는 하위 문제 (코인 변경 문제)

DP에 대한 재귀 솔루션을 찾기 전에 문제의 하위 문제를 식별하십시오. 각 하위 문제는 상위 문제와 동일하므로 동일한 알고리즘이 적용됩니다.

분모, d [] 및 sum, S의 목록이 제공되는 동전 변경에 대한 예를 들어 보자. 우리는 S까지 합산하기 위해 최소 교단 수, (교단 수)를 찾아야합니다. 카운트를 찾기위한 솔루션 (방법)을 정의 int findMinDenom (int [] d, int S). 이 시점에서 우리는 어떤 구현이 될지는 모르지만 문제에 필요한 매개 변수는 d와 S입니다.

하위 문제는 해결 방법은 같지만 합계는 더 낮습니다. 따라서 findMinDenom이 각 하위 문제를 해결하는 방식으로 구현하려고합니다. 이것은 우리가 더 낮은 합계를 가진 동일한 메소드를 호출하는 재귀 솔루션으로 이어질 것입니다.

int findMinDenom(int[] d, int S) {
  if (S == 0) {
    // If Sum is zero, then no denomination is required.
    return 0;
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenom(d, s); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  return result;
}

DP를 사용하여 방금 해결했습니다. 그러나 메모는 없습니다. 배열을 사용하여 결과를 유지하는 방법을 소개합니다. 하위 문제가 이미 해결되지 않았기 때문입니다. 그렇다면 해당 하위 문제의 결과를 반환하십시오. 합계 0의 경우 교파는 0이됩니다. 솔루션 [0] = 0이 있으며 문제 S에 대한 솔루션을 코딩 용어로 솔루션 [S]로 찾고자합니다. 따라서 솔루션 배열의 크기는 S + 1입니다.

// Initialize solution
int[] solution = new int[S+1];
solution[0] = 0; 
for (int i = 1; i <= S; i++)
  solution[i] = -1; // Just to denote that solution is not found yet.

이제 재귀 방법의 솔루션을 전달하십시오.

int findMinDenomMemo(int[] d, int S, int[] solution) {
  if (solution[S] > -1) {
    // Solution exists
    return solution[S];
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenomMemo(d, s, solution); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  // Just now solved for sub problem S. So store it.
  solution[S] = result;
  return result;
}