2008 - Pathfinger. Méthode employée ?

Bonjour.

J'ai codé la fonction pour le pathfinger.
Je cite :
"On dispose d'une matrice de taille n*n. En partant de (1, 1) (le coin supérieur gauche), vous devez trouver le chemin allant au coin inférieur droit (n, n) dont la somme des cases par lesquelles il passe est la plus grande possible.

Attention : vous pouvez seulement vous déplacer vers la droite ou vers le bas."

Elle fonctionne correctement mais je dépasse la limite de temps.
La fonction prend tout les chemins possibles et lorsque qu' "elle" arrive au point n, n elle regarde si la somme est supérieur au maximum trouvé jusque là.
Elle fonctionne par récurrence.

Voici la fonction (je la post vu que de toute manière elle n'est pas la bonne)
int max = 0;
int somme = 0;

void pathfinder(int size, int **tab, int ligne, int colonne)
{
somme += tab[ligne][colonne];

if (ligne + 1 pathfinder (size, tab, ligne+1, colonne);

if (colonne + 1 pathfinder (size, tab, ligne, colonne+1);

if (ligne == size-1 && colonne == size-1 && somme > max)
max = somme;

somme -= tab[ligne][colonne];
}

En fait je ne voie par d'autres méthodes possibles. Ma question est donc :
Est-ce ma méthode qui est en cause (càd étudier toutes les possibilités) ou le codage (par exemple utiliser la récurrence) ?

Merci d'avance

PS: Ne me donnez pas la solution mais plutôt des indices :p

c'est parce que tu vas au bout de chaque chemin, alors que tu pourrais parfois t'arrêter avant (quand tu vois que tu as déjà fait mieux pour arriver au même endroit).

ps : pathfinDer et pas finger :p

Hum okay. Je ne sais par contre pas encore comment mettre ça en place car je ne vois pas comment ne peut pas savoir si la suite (du parcours) va permettre d'augmenter fortement la somme ou non.
Il va falloir que je change de méthode où je stocke de nouvelles données.
Ca aurait été plus simple de calculer le minimum :p

Merci ;)

Ca aurait été plus simple de calculer le minimum :p

Pourquoi ? C'est exactement la même chose.

Exécute ton algorithme à la main, sur une petite grille (4*4 par exemple), sans tricher. N'as-tu pas l'impression de faire les mêmes calculs encore et encore ? Ne peux-tu pas mémoriser certaines choses pour éviter ce problème ?

Pourquoi ? C'est exactement la même chose.

Parce que dès que la somme aurait été > au minimum j'aurai arêter de chercher plus loin et ça réduirait le temps de calcul.

Sinon j'ai fait ce que tu m'as dis. Effectivement des calculs se répètent mais je ne voie pas encore comment faire pour éviter cela ;)
(Enfin j'ai peut-être une idée en stockant d'autre information sur chaque cellule grâce à des structures \^\^)

Merci

Ou sinon, tu peux modifier ton approche dans la façon de parcourir la matrice. :)

ben ,c normal, use loops,
i did it with a loop,
here is codes:

[édité par Thomas Deniau pour supprimer le code source d'une solution : merci de ne pas donner les solutions sur ce forum. Les indices sont les bienvenus cependant ! / edited by Thomas Deniau to delete the source code of a solution : please do not post solutions on this forum. Hints are welcome though]