Programmation Java : Programmation Dynamique sur les escaliers exemple

Un homme est en cours d'exécution jusqu'à un escalier de n étapes, et peut aller soit étapes 1, 2, ou 3 étapes à la fois. Maintenant écrire un programme pour compter le nombre de façons possibles de l'enfant peut courir dans les escaliers.

Le code donné est comme ci-dessous

public static int countDP(int n, int[] map) {
 if (n<0)
   return 0;
 else if (n==0)
   return 1;
 else if (map[n]>-1)
   return map[n];
 else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; }
 }

Je sais que C et C++, pas de JAVA.
C'est à partir de la Fissuration du Codage entrevue livre.
Quelqu'un pourrait-il peut expliquer

  1. pourquoi et comment elle se sert de la fonction de carte ici? carte ici est la matrice de droite?

  2. Je ne vois pas de ligne pour gagner une entrée à la carte de tableau mais comment en serait-il de retour quelque chose?

  3. Quelqu'un a une idée de C++ ou C version de ce code? Il est difficile de comprendre ce code. Peut-être pas à cause de la JAVA de la grammaire, mais l'implicite de la structure de la programmation dynamique.

  4. Ce serait le moment de la complexité de cet algorithme? Il devrait être plus petit que O(3^n) ?

Je vous en serais très reconnaissante.

Merci, les gars

  • Connexes: stackoverflow.com/questions/12255193/...
  • je vais faire de mon mieux avec l' (cryptique) question: 1. la carte est un int tableau. 2. il doit avoir été défini de l'extérieur c'est à dire pas dans cet exemple et doit contenir n+1 éléments 3. non, si vous voulez, c'répondu que vous aurez à ajouter C et C++ pour les balises 4. ...
InformationsquelleAutor | 2013-07-22