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
-
pourquoi et comment elle se sert de la fonction de carte ici? carte ici est la matrice de droite?
-
Je ne vois pas de ligne pour gagner une entrée à la carte de tableau mais comment en serait-il de retour quelque chose?
-
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.
-
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 à ajouterC
etC++
pour les balises 4. ...
Vous devez vous connecter pour publier un commentaire.
Ok, c'est ce que fait le code.
Si il n'y a pas assez d'étapes restantes, puis ne pas le compter. Par exemple, si il y a deux étapes restantes, mais l'utilisateur est en train d'essayer de prendre les trois étapes, alors il ne compte pas comme une combinaison possible.
else if (n==0)
return 1;
Si le nombre d'étapes matches restants, le nombre de mesures disponibles, l'utilisateur est en train d'essayer de prendre, il est une combinaison possible. Donc, de retour de 1 parce que c'est une combinaison possible et doit être ajouté au nombre total de combinaisons valides.
else if (map[n]>-1)
return map[n];
Ici est la dynamique de la partie programmation. Supposons que toutes les valeurs dans le tableau a une valeur de -1. Ainsi, si le nombre est supérieur à -1, il a déjà été résolu, donc de retour le nombre total de combinaisons à partir de l'étape numéro n au lieu de le résoudre.
return map[n]; }
Enfin, cette partie permet de résoudre le code. Le nombre de combinaisons possibles est égal au nombre de combinaisons possibles, l'utilisateur peut obtenir si il prend 1 étape + le nombre de combinaisons possibles, l'utilisateur peut obtenir s'il prend 2 étapes + le nombre de combinaisons possibles, l'utilisateur peut obtenir s'il prend trois étapes.
Un exemple, supposons qu'il y a 5 étapes
Une course simple serait:
Le livre montre une dynamique de programmation technique appelée memoization. Il est utilisé pour éviter le calcul le même nombre de nouveau: si l'élément n'est pas
-1
, puis il a été calculé à nouveau, et le calcul, cela signifierait perdre beaucoup de cycles de PROCESSEUR. DP calcule la valeur une fois, puis le retourne à chaque fois que la valeur est nécessaire.Correct,
map
est de type tableau.Que serait l'attribution de la troisième ligne à partir du bas:
Droit, DP et memoization prendre un certain temps pour s'y habituer. Courir à travers cet algorithme une fois avec du papier et un crayon pour un petit nombre, disons, 10. Cela va vous montrer comment la sous-structure optimale de la réponse aide de cet algorithme trouver la réponse si rapide.
Absolument! Chaque élément est calculée exactement une fois, et chaque élément prend amorti
O(1)
, de calculer, de sorte que la complexité globale de ce code estO(N)
. Cela peut être contre-intuitif, comme vous l'observez comment la chaîne de récursive des invocations pour calculercountDP(K)
prend unO(K)
récursive des invocations. Cependant, chaque invocation termine le calcul deK
éléments de lamap
(notezmap
est une rue à sens unique: une fois que vous définissez une valeur non-négative dans une cellule, il va rester non-négative pour toujours, donc re-calcul de la même valeur par tout autre chemin d'accès d'appel aurait la mêmeO(1)
temps.1.) la carte est un tableau d'entiers. La notation en Java, c'est que la carte[n] retourne la valeur entière à l'indice n.
2.) Le retour est un entier, car map[n] retourne la valeur entière à l'indice n. La seule fois où une valeur est enregistrée dans le tableau est à
C'est un appel récursif pour trouver la somme des mesures en comptant tous les possibles 1 , 2, et 3 combinaisons.
3.)
4.) Oui la complexité serait beaucoup plus rapide que O(3^n).
JavaScript solution: ( itératif )
//la réponse de 4 a 14 ans et de 5 à 27. Pour la ligne est commentée. Quelqu'un peut-il commenter pourquoi mon processus de pensée ont eu tort?