>

동적 프로그래밍 질문에 대한 올바른 직관을 개발하려고하지만 질문의 특정 측면을 이해할 수 없습니다.

leetcode https://leetcode.com/problems/coin-change/

많은 튜토리얼에서이 방법과 같은 상향식 접근법이 언급되어 있습니다- https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/

이 접근법에서는 최적의 솔루션에서 시작하여 솔루션을 향한 어레이를 구축합니다. 예-우리는 합계 2와 3 등을 찾는 최적의 솔루션을 찾습니다. 결국 우리는 해결책을 갖게 될 것입니다. 이것이 내가 이해하는 접근법입니다.

기억으로 다른 재귀 접근 방식으로 머리를 감싸는 데 어려움을 겪고 있습니다. 문제에 대한 역 추적 접근 방식을 작성했지만 메모를 적용하는 방법을 잘 모르겠습니다.

public int changeCoins_BT(int[] coins, int target, int min, int num_curr) {
    if(target == 0) {
        return min < num_curr ? min : num_curr;
    } else if(target < 0) return min;
    else if(num_curr > min) return min;
    for(int i=0;i<coins.length;i++) {
        min = changeCoins_BT(coins,target-coins[i],min,num_curr+1);
    }
    return min;
}


  • 답변 # 1

    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;
    }
    
    

  • 이전 python - saveFrame에서 NullPointerException 오류가 발생 함
  • 다음 javascript - 객체 [키]가 전제 조건을 충족하는 Foreach 키