Meditasi LeetCode: Perubahan Syiling

Mari kita mulakan dengan penerangan untuk masalah ini:

Anda diberi syiling susunan integer yang mewakili syiling denominasi berbeza dan jumlah integer mewakili jumlah wang.

Pulangan bilangan syiling paling sedikit yang anda perlukan untuk menambah jumlah itu. Jika jumlah wang itu tidak boleh dibuat dengan sebarang kombinasi syiling, pulangkan -1.

Anda mungkin menganggap bahawa anda mempunyai nombor tidak terhingga bagi setiap jenis syiling.

Contohnya:

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

Atau:

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

Atau:

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

Selain itu, salah satu kekangan kami menunjukkan bahawa 1 <= syiling.panjang <= 12.

---

Masalah ini sebenarnya sudah biasa dan anda mungkin pernah melihatnya dalam konteks masalah tamak. Walau bagaimanapun, versi ini memerlukan kami mencari bilangan syiling paling sedikit, dan pendekatan tamak tidak akan berjaya.
Sebab itu benar ditunjukkan dengan kemas dalam video NeetCode: contohnya, jika syiling kami [1, 3, 4, 5] dan jumlahnya ialah 7, pendekatan tamak akan mendapat 5 dahulu, kemudian ia akan mencuba semua maksimum amaun sehingga ia perlu berpuas hati dengan dua 1, menjadikannya jumlah 5, 1 dan 1. Walau bagaimanapun, kita boleh menggunakan lebih sedikit syiling daripada itu: 4 dan 3. Jadi, mari lihat bagaimana kita boleh melakukannya melakukan itu.

Kita perlu membina sehingga jumlah entah bagaimana, untuk bilangan minimum syiling yang boleh kita gunakan. Untuk itu, mari kita mulakan dengan memulakan tatasusunan:

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




</p>
<p>Kami mempunyai tatasusunan jumlah panjang + 1 ini kerana <mark>setiap indeks akan memegang bilangan minimum syiling yang boleh kami gunakan untuk setiap jumlah.</mark> Contohnya, indeks 0 tatasusunan dp kami akan memegang nilai syiling bilangan minimum syiling yang boleh kita gunakan untuk jumlah 0; begitu juga, indeks 7 akan memegang nilai bilangan minimum syiling yang boleh kita gunakan untuk jumlah 7.</p>

<p>Kami memulakan setiap indeks dengan nilai pemegang tempat amaun + 1, kerana bilangan maksimum syiling tidak boleh melebihi jumlah (contohnya, bilangan maksimum syiling yang boleh kami gunakan untuk 7 ialah 7: 1 + 1 + 1 + 1 + 1 + 1 + 1).</p>

<div class="table-wrapper-paragraph"><table>
<thead>
<tr>
<th>Note</th>
</tr>
</thead>
<tbody>
<tr>
<td>The minimum valued coin is 1 in this problem, as one of the constraints indicates.</td>
</tr>
</tbody>
</table></div>

<p>Untuk jumlah 0, bilangan minimum syiling yang boleh kami gunakan adalah jelas: 0:<br>
</p>

<pre class="brush:php;toolbar:false">dp[0] = 0;

Kemudian, kami akan mengulangi tatasusunan ini, bermula dari indeks 1, dan untuk setiap indeks, kami akan mengulangi melalui syiling:

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

Jika syiling yang kami lihat boleh digunakan untuk jumlah tersebut (iaitu amountIdx - syiling >= 0), maka kami akan mengemas kini nilai untuk jumlah tersebut dalam tatasusunan dp kami. Ia akan menjadi nilai minimum sama ada nilai yang telah kita miliki atau 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.

Atas ialah kandungan terperinci Meditasi LeetCode: Perubahan Syiling. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!