Comment cette solution est-elle un exemple de programmation dynamique?

Question

Un conférencier a donné à cette question en classe: [question]

Une séquence de nombres entiers n est stocké dans un tableau A [1..n]. Un entier a en A est appelé la majorité si elle apparaît plus à n/2 fois dans A.

Un algorithme O (n) peut être conçu pour trouver la majorité sur la base du suivant observation: si deux différents éléments de la séquence originale sont supprimés, puis la majorité dans la séquence originale reste la majorité dans la nouvelle séquence . En utilisant cette observation, ou autrement, écrire le code de programmation à trouver la majorité, s'il en existe, en O (n) temps.

pour laquelle cette solution a été acceptée [solution]

int findCandidate(int[] a) 
{ 
    int maj_index = 0; 
    int count = 1; 
    for (int i=1;i<a.length;i++) 
    { 
     if (a[maj_index] == a[i]) 
      count++; 
     else 
      count--; 

     if (count == 0) 
     { 
      maj_index =i; 
      count++; 
     } 
    } 
    return a[maj_index]; 
} 

int findMajority(int[] a) 
{ 
    int c = findCandidate(a); 
    int count = 0; 
    for (int i=0;i<a.length;i++) 
     if (a[i] == c) count++; 

    if (count > n/2) return c; 
    return -1;//just a marker - no majority found 
} 

Je ne vois pas comment la solution fournie est une solution dynamique. Et je ne vois pas comment, sur la base du libellé, il a sorti ce code.

Answer 1

Il s'agit d'une programmation dynamique car la fonction findCandidate décompose le tableau fourni en parties plus petites et plus gérables. Dans ce cas, il commence avec le premier tableau en tant que candidat pour la majorité. En augmentant le nombre quand il est rencontré et en diminuant le compte quand ce n'est pas le cas, il détermine si cela est vrai. Lorsque le compte est égal à zéro, nous savons que les premiers caractères ne sont pas majoritaires. En calculant continuellement la majorité locale, nous n'avons pas besoin de parcourir le tableau plus d'une fois dans la phase d'identification des candidats. Nous vérifions ensuite si ce candidat est réellement la majorité en passant une deuxième fois dans le tableau, en nous donnant O (n). Il fonctionne réellement dans 2n fois, puisque nous itérons deux fois, mais la constante n'a pas d'importance.

Answer 2

'Dynamic programming' n'a rien à voir avec l'allocation dynamique de la mémoire ou quoi que ce soit, c'est juste un vieux terme. En fait, cela n'a pas grand chose à voir avec les mesures modernes de «programmation».

Il s'agit d'une méthode de résolution de la classe spécifique de problèmes - quand une solution optimale de sous-problème est garantie de faire partie de la solution optimale de plus gros problème. Par exemple, si vous voulez payer 567 $ avec le plus petit montant de factures, la solution contiendra au moins une des solutions pour 1 $. 566 $ et une facture de plus.

Le code est juste une application de l'algorithme.

Answer 3

Le origin of the term dynamic programming essaie de décrire une façon vraiment géniale d'optimiser certains types de solutions (la dynamique était utilisée car elle semblait plus puissante). En d'autres termes, lorsque vous voyez "programmation dynamique", vous devez le traduire en "optimisation impressionnante".