Tabulation : rendre la monnaie

Le plus petit nombre de pièces pour former un montant : l'exemple type d'une DP en tableau à une dimension.

État : dp[a] = plus petit nombre de pièces pour faire le montant a. Transition : dp[a] = 1 + min(dp[a - pièce]) sur toutes les pièces utilisables. Base : dp[0] = 0. Complexité O(montant × nombre de pièces).

Piège : le glouton (prendre toujours la plus grande pièce) est faux en général : avec les pièces {1, 3, 4} et un montant de 6, il donne 4+1+1 (3 pièces) alors que 3+3 en suffit de 2.

function coinChange(coins: number[], amount: number): number {
  const dp = new Array<number>(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];   // -1 : montant impossible
}