1. C'est le coup classique : les cases du tableau card sont initialisées à zéro (par la création new int[m+1]).

  2. Il s'agit d'une boucle dont le corps est vide. L'effet est de calculer i0 minimal tel que di0n.

    La boucle termine fatalement, soit parce qu'il existe un di inférieur ou égal à n, soit parce que i dépasse k-1 auquel cas il se produit une erreur.

  3. Voyons accès par accès.

  4. Le coût est en O(m × k), m tours de la boucle 6-18 qui contient essentiellement une boucle à k tours.

  5. La correction repose sur la formule :
    M(0) = 0,    M(n) = 1+
     
    min
    dis
    M(n-di)


  6. Il a deux façons de procéder, la première repose sur l'enregistrement, dans un tableau idoine, de l'espèce di pour laquelle on a M(n) = M(n-di)+1.
      static int [] dynamiqueCard(int [] d, int m) {
        
    int k = d.length ;
        
    int [] card = new int [m+1] ;
    •••    
    int [] esp = new int [m+1] ;

        card[0] = 0 ; 
    // Inutile en Java
        
    for (int n = 1 ; n <= m ; n++) {
          
    int r = m+1 ;
          
    int i ;
          
    for (i = 0 ; d[i] > n ; i++)
            ;
          
    for (; i < k ; i++) {
            
    int di = d[i] ;
            
    if (card[n-di]+1 < r) {
              r = card[n-di]+1 ;
    •••          esp[n] = i ;
            }
          }
          card[n] = r ;
        }
        
    return card ;
      }
    Une fois rempli le tableau esp, on reconstitue facilement un paiement optimal de m :
      int r = new int[k] ;

      
    while (m > 0) {
        
    int i = esp[m] ;
        r[i]++ ; 
    // Pour r[i] = r[i]+1 ;
        m -= d[i] ;
      }

    On peut en fait, comme souvent en programmation dynamique, se passer du tableau esp en reconstituant les éléments intéressants à partir du tableau des cardinaux minimaux. Sur ce principe, voici une méthode qui renvoie un paiement optimal.
      static int [] dynamique(int [] d, int m) {
        
    int k = d.length ;
        
    int [] card = dynamiqueCard(d, m) ;
        
    int [] r = new int[k] ;
        
    while (m > 0) {
          
    int c = card[m] ;
          
    int i ;
          
    for (i=0 ; d[i] > m ; i++)
            ;
          
    for ( ; ; i++) {
            
    int di = d[i] ;
            
    if (card[m-di] == c-1) {
              m -= di ; r[i]++ ;
              
    break ;
            }
          }
        }
        
    return r ;
      }
    On notera l'économie d'un tableau de taille environ m pour un prix somme toute modique en temps de calcul.

    La boucle for ( ; ; i++)... est remarquable, car elle n'a pas de condition. Dans ce cas, la condition est vraie, de sorte que la tournure idiomatique pour la boucle « infinie » est :
      for ( ; ; ) {
        …
      }

    Bon tout ça est très culturel, mais en fait rien ne nous empêche de parcourir le tableau d de la droite vers la gauche. Le code devient alors un peu plus simple.
      static int [] dynamique(int [] d, int m) {
        
    int k = d.length ;
        
    int [] card = dynamiqueCard(d, m) ;
        
    int [] r = new int[k] ;
        
    while (m > 0) {
          
    int c = card[m] ;
          
    for (int i = k-1 ; ; i--) { // Pas de condition
            
    int di = d[i] ;
            
    if (card[m-di] == c-1) { // Car di tel que card[m-di] == c-1 existe
              m -= di ; r[i]++ ;
              
    break ;
            }
          }
        }
        
    return r ;
      }