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 つは、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]);
    }
  }
}

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 中国語 Web サイトの他の関連記事を参照してください。