Rendu de monnaie optimal

let rendu_min pieces montant =
  let infini = montant + 1 in
  let m = Array.make (montant + 1) infini in
  m.(0) <- 0;
  for s = 1 to montant do
    List.iter (fun p ->
      if p <= s && m.(s - p) + 1 < m.(s) then m.(s) <- m.(s - p) + 1
    ) pieces
  done;
  if m.(montant) = infini then -1 else m.(montant)

rendu_min [4;3;1] 6 : m.(6) se calcule via m.(3) + 1 (et m.(3) = 1), soit 2. La DP trouve l'optimum $3+3$, contrairement au glouton.