LeetCode 명상: 코인 변경

이 문제에 대한 설명부터 시작하겠습니다.

다양한 액면가의 동전을 나타내는 정수 배열 동전과 총 금액을 나타내는 정수 금액이 제공됩니다.

해당 금액을 보충하는 데 필요한 최소 개수의 코인을 반환합니다. 해당 금액을 코인 조합으로 채울 수 없는 경우 -1을 반환합니다.

각 코인의 수는 무한하다고 가정할 수 있습니다.

예:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

또는:

Input: coins = [2], amount = 3
Output: -1

또는:

Input: coins = [1], amount = 0
Output: 0

또한 제약 조건 중 하나는 1

---

이 문제는 사실 익숙한 문제이고 탐욕스러운 문제의 맥락에서 본 적이 있을 것입니다. 하지만 이 버전에서는 가장 적은 수의 코인을 찾아야 하며 탐욕스러운 접근 방식은 작동하지 않습니다.
이것이 사실인 이유는 NeetCode 비디오에 깔끔하게 나와 있습니다. 예를 들어, 코인이 [1, 3, 4, 5]이고 금액이 7인 경우 탐욕스러운 접근 방식은 5를 먼저 얻은 다음 모든 최대 2개의 1로 만족해야 할 때까지 총 5, 1, 1이 됩니다. 하지만 그보다 적은 수의 코인(4, 3)을 사용할 수 있습니다. 그럼 어떻게 진행되는지 살펴보겠습니다. 그렇게 하고 있어요.

우리가 사용할 수 있는 최소한의 코인을 위해 어떻게든 금액을 늘려야 합니다. 이를 위해 배열 초기화부터 시작해 보겠습니다.

let dp = Array.from({ length: amount + 1 }, () => amount + 1);

각 인덱스가 각 금액에 사용할 수 있는 최소 동전 수를 보유하므로 길이 금액 + 1의 배열이 있습니다. 예를 들어 dp 배열의 인덱스 0은 0에 사용할 수 있는 최소 코인 수; 마찬가지로 인덱스 7은 7에 사용할 수 있는 최소 코인 수의 값을 보유합니다.

최대 코인 수는 amount를 초과할 수 없으므로 자리 표시자 값 amount + 1로 각 인덱스를 초기화합니다(예를 들어 7에 사용할 수 있는 최대 코인 수는 7: 1 + 1 + 1 + 1 + 1 + 1 + 1).

Note

The minimum valued coin is 1 in this problem, as one of the constraints indicates.

금액이 0인 경우 사용할 수 있는 최소 코인 수는 0:
입니다.

dp[0] = 0;

그런 다음 인덱스 1부터 시작하여 이 배열을 반복하고 각 인덱스에 대해 동전을 반복합니다.

for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
  for (const coin of coins) {
    /* ... */
  }
}

우리가 보고 있는 코인이 해당 금액에 사용될 수 있는 경우(즉, amountIdx - coin >= 0) dp 배열에서 해당 금액에 대한 값을 업데이트합니다. 이미 가지고 있는 값 또는 1 + dp[amountIdx - coin]:
중 최소값이 됩니다.

for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
  for (const coin of coins) {
    if (amountIdx - coin >= 0) {
      dp[amountIdx] = Math.min(dp[amountIdx], 1 + dp[amountIdx - coin]);
    }
  }
}

Note

The reason for 1 + dp[amountIdx - coin] is that we use the solution to an already calculated value, reusing the subproblem. So, 1 is the coin we're currently considering.

If, at the end, we can't match the total amount with any combination of coins, we have to return -1.
The way to check for that is to check the condition where the last element equals amount + 1. In that case, we can return -1. Otherwise, we'll just return the last element which holds the minimum number of coins that make up the amount:

function coinChange(coins: number[], amount: number): number {
  /* ... */

  if (dp[dp.length - 1] === amount + 1) {
    return -1;
  }

  return dp[dp.length - 1];
}

And, here is the final solution:

function coinChange(coins: number[], amount: number): number {
  let dp = Array.from({ length: amount + 1 }, () => amount + 1);
  dp[0] = 0; 

  for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
    for (const coin of coins) {
      if (amountIdx - coin >= 0) {
        dp[amountIdx] = Math.min(dp[amountIdx], 1 + dp[amountIdx - coin]);
      }
    }
  }

  if (dp[dp.length - 1] === amount + 1) {
    return -1;
  }

  return dp[dp.length - 1];
}

Time and space complexity

The time complexity is $O(n\ast m)$O(n∗m) where $n$n is the amount + 1 and $m$m is the number of coins we have. We iterate through each value up to amount + 1, and for each of those values, iterate again through each coin, doing a constant operation.

The space complexity depends on the amount we're given as the size of our dp array will grow as the amount increases, so we can say that it's $O(n)$O(n) where $n$n is the amount.

---

It's time for a deep breath. Even though we usually make peace with the solutions to dynamic programming problems, it's tough getting them in the first place — not only coming up with the solutions, but also understanding the already existing ones.

Next, we'll take a look at the problem Maximum Product Subarray. Until then, happy coding.

위 내용은 LeetCode 명상: 코인 변경의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!