Pyramides - Demi Finale 2010

Bonjour à tous,
je suis plutôt débutant en algorithmie, et j'ai été sélectionné pour les demi-finales (à Lyon), donc j'mentraine gentiment histoire de pas me faire insulter ... :p
Je dépasse les limites du temps pour l'exercice sur les pyramides, j'me demandais donc s'il y avait une meilleure méthode que la brute force (=essayer toutes les possibilités et donc la complexité doit être qqc comme O(2\^N) avec N qui peut monter jusqu'à 100 ... *sifflote*)
Dans le même "niveau" j'ai réussi Divination plutôt facilement, donc j'pense que y'a un truc que j'dois pas savoir faire :'(
Merci d'avance pour votre aide ;)
A bientôt !

Programmation dynamique ;)

Il y a beaucoup plus simple : Tu peux calculer le coefficient d'adhérence pour chaque étage à partir de l'étage du dessus!

Bah ca ressemble à de la programmation dynamique non?

Perso, à l'époque, j'avais commencer par le bas : en numérotant les étages de 0 (celui tout en bas) à N-1 (celui d'en haut) :
* Pour n=0, tu as déjà les coeff d'adhérences pour aller en bas : C'est directement celle de la marche
* Pour n≥0, tu supposes savoir avoir déjà pour l'étage n et pour chaque marche, le coeff maximal pour aller en bas. Après, pour chaque bloc de l'étage n+1, tu prends le max des coeff des 2 blocs qui sont juste en dessous et tu lui ajoutes le coeff de ton bloc.
Par récurrence, pour le bloc d'en haut, tu as le coeff maximal, que tu n'as plus qu'à renvoyer.
Complexité : O(N²)

"Il y a beaucoup plus simple : Tu peux calculer le coefficient d'adhérence pour chaque étage à partir de l'étage du dessus!" cube45

Merci j'y avais pas pensé =/
Merci aux autres aussi, même si je connais pas la "programmation dynamique" et que j'ai pas trop compris ton raisonnement johnatan ;)

C'est un peu ce que disait cube45, mais à partir de l'étage d'en dessous !
Par exemple :
--5--
-2-7-
4-6-3
Le but, c'est de refaire une pyramide mais avec les max des coeff pour aller en bas.
Ainsi, premier passage : (Les 0, c'est qu'on a pas encore traiter)
--0--
-0-0-
4-6-3
Deuxième passage :
--0--
-8-15-
4-6-3
Avec 8 = 2 + max(4;6) et 15 = 7 + max(6;3)
Troisième passage :
--20--
-8-15-
4-6-3
car 20 = 5 + max(8;15)
Donc tu renvois 20 :)

renvoies*
(JJ, à quand le nouveau classement des floodeurs ?!)

Ah ouai OK johnathan ! Compris ;)

Mon prénom massacré deux fois T_T

* Offre une corde à johnathan ...

* Offre un h à Johnathan

Autant que je desinstalle ubuntu pour être sur Windows, ça ira plus vite …

Bah, quitte à changer d'OS, prend en un bien au moins.
Longue vie à MultiDeskOS !! Le seul OS qui s'approche de la perfection, les autres ne pourront jamais le rattraper !

@baillouaja: je connaissais pas non plus la programmation dynamique avant de voir ton post et maintenant j'ai bien compris, fait des schémas sur papier et va lire des trucs (wikipédia m'a un peu aidé). Bonne chance, on se verra à Lyon :d

Pas sur que lui donner carrément la solution soit une grande aide, m'enfin...

Si ! ça m'a permis de voir le problème différement, je suis sûr que ça me servira dans d'autres problèmes ;)