Chemin de coût minimal dans une grille

let chemin_min cout =
  let n = Array.length cout and m = Array.length cout.(0) in
  let dp = Array.make_matrix n m 0 in
  dp.(0).(0) <- cout.(0).(0);
  for j = 1 to m - 1 do dp.(0).(j) <- dp.(0).(j - 1) + cout.(0).(j) done;
  for i = 1 to n - 1 do dp.(i).(0) <- dp.(i - 1).(0) + cout.(i).(0) done;
  for i = 1 to n - 1 do
    for j = 1 to m - 1 do
      let h = if dp.(i - 1).(j) <= dp.(i).(j - 1) then dp.(i - 1).(j) else dp.(i).(j - 1) in
      dp.(i).(j) <- h + cout.(i).(j)
    done
  done;
  dp.(n - 1).(m - 1)

On arrive en (i,j) par le haut ou par la gauche : on prend le moins coûteux, plus le coût de la case. La première ligne et la première colonne (un seul chemin possible) servent de cas de base. Coût $\Theta (nm)$.