Méditations LeetCode : changement de pièces

Commençons par la description de ce problème :

Vous recevez un tableau de pièces entières représentant des pièces de différentes dénominations et un montant entier représentant une somme d'argent totale.

Rendez le moins de pièces dont vous avez besoin pour compenser ce montant. Si cette somme d'argent ne peut être compensée par aucune combinaison de pièces, renvoyez -1.

Vous pouvez supposer que vous possédez un nombre infini de chaque type de pièce.

Par exemple :

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

Ou :

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

Ou :

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

De plus, une de nos contraintes indique que 1 <= coins.length <= 12.

---

Ce problème est en fait familier, et vous l'avez peut-être vu dans le contexte d'un problème gourmand. Cependant, cette version nous oblige à trouver le moins nombre de pièces, et une approche gourmande ne fonctionnerait pas.
Pourquoi cela est vrai est clairement montré dans une vidéo NeetCode : par exemple, si nos pièces sont [1, 3, 4, 5] et que le montant est 7, l'approche gourmande obtiendra 5 en premier, puis elle essaiera tous les maximum jusqu'à ce qu'il doive se contenter de deux 1, ce qui fait un total de 5, 1 et 1. Cependant, nous pouvons utiliser moins de pièces que cela : 4 et 3. Voyons donc comment nous pourrions procéder faire ça.

Nous devons augmenter le montant d'une manière ou d'une autre, pour le nombre minimum de pièces que nous pouvons utiliser. Pour cela, commençons par initialiser un tableau :

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




</p>
<p>Nous avons ce tableau de longueur montant + 1 car <mark>chaque index contiendra le nombre minimum de pièces que nous pouvons utiliser pour chaque montant.</mark> Par exemple, l'index 0 de notre tableau dp contiendra la valeur du nombre minimum de pièces que nous pouvons utiliser pour un montant de 0 ; de même, l'indice 7 contiendra la valeur du nombre minimum de pièces que nous pouvons utiliser pour le montant de 7.</p>

<p>Nous initialisons chaque index avec la valeur d'espace réservé montant + 1, car le nombre maximum de pièces ne peut pas dépasser le montant (par exemple, le nombre maximum de pièces que nous pouvons utiliser pour 7 est 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>Pour le montant de 0, le nombre minimum de pièces que nous pouvons utiliser est évident : 0 :<br>
</p>

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

Ensuite, nous parcourrons ce tableau, en commençant par l'index 1, et pour chaque index, nous parcourrons les pièces :

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

Si la pièce que nous examinons peut être utilisée pour ce montant (c'est-à-dire montantIdx - pièce >= 0), alors nous mettrons à jour la valeur de ce montant dans notre tableau dp. Ce sera le minimum soit de la valeur que nous avons déjà, soit de 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.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!