Déterminer une relation de récurrence

[fatal_error]

honnetement, je pense que tu tournes en rond et ca sert rien de continuer la douleur plus loin

Code: Tout sélectionner

 def bottomup(self, t, c, a, b, i=-1):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth > i:
        tmp = [0] * (depth + 1)

        for k in range(i + 1, depth + 1):

            if depth == k:
                ab = b
            elif c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        keep = tmp
        depth -= 1

    return keep


1: tjs avec ton i=-1 qui sert à rien, donc simplifions la tache

Code: Tout sélectionner

 def bottomup(self, t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth + 1)

        for k in range(i, depth + 1):

            if depth == k:
                ab = b
            elif c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        keep = tmp
        depth -= 1

    return keep


2)

tu fais ton for que sur les symboles avant et tu rajoutes apres le cas du V(depth, _)

Code: Tout sélectionner

 def bottomup(self, t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth + 1)

        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[depth], b * t[depth] + keep[depth])
        keep = tmp
        depth -= 1

    return keep


fini

3) tu fixes la taille de tmp parce que ca représente pas la taille de ce que tu dois stocker dedans: tu dois stocker les symboles avant plus V(depth,'_') donc: depth-i+1 elem et non depth +1

Code: Tout sélectionner

 def bottomup(self, t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)

        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[depth], b * t[depth] + keep[depth])
        keep = tmp
        depth -= 1

    return keep


ca change probablement rien mais c'est mieux d'être précis parce que tu t'évites des emmerdes potentielles

4) tu simplifies ton problème (et c'est pas faute de le dire!):

Code: Tout sélectionner

t = [3, 9, 3]
c = [2, 2, 2]
a, b = (2, -5)


5)tu calcules A LA MAIN
V(2,0) = max(0, A*3)
V(2,1) = max(0, A*3)
V(2,_) = 0
donc apres l'itération à n-1, tu t'attends à voir tmp == [6,6,0]

Code: Tout sélectionner

def bottomup(t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[depth], b * t[depth] + keep[depth])
        print('depth: ', depth, tmp)
        keep = tmp
        depth -= 1
    return keep
t = [3, 9, 3]
c = [2, 2, 2]
a, b = (2, -5)

print(bottomup(t, c, a, b))
#depth:  2 [6, 6, 0]
osef depth:  1 [24, 6]
osef depth:  0 [24]
osef [24]



c'est le cas...
tu continues à la main...

V(1,0) = max(0 + V(2,0), A*9 + V(2, 1) ) = max(6, 18+6) = 24
V(1,'_') = max(0 + V(2,'_'), B*9 + V(2, 1) ) = max( 0, -45+6 ) = 0
tu t'attends à la deuxième iteration à avoir tmp==[24,0]
OR tu as [24,6] donc la ligne tmp[depth] = max(0 + keep[depth], b * t[depth] + keep[depth]) est fausse

Code: Tout sélectionner

    ...
    while depth >= i:
        tmp = [0] * (depth -i + 1)
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[depth], b * t[depth] + keep[depth])
        if depth == 1:
            print('failing for ', keep[depth], b*t[depth]+keep[depth])
            print(tmp)

        keep = tmp
        depth -= 1
    ...
#failing for  6 -39
#[24, 6]



tu constates que keep[depth] vaut 6 alors que ca devrait valoir 0. donc probablement tu tapes pas sur le bon indice.
depth == 1, et tu devrais taper sur la fin de keep qui est [6,6,0]: donc depth == 2.
donc tu corriges
pour depth==1 il faut taper dans le deuxieme elem de keep
mais pour depth==2, il keep est de taille 2 et il faut taper dans le deuxieme elem (qui vaut tous 0)
donc soit tu initialises keep avec une taille 3, soit tu prends le dernier elem qui dans le cas de spécial de depth2 vaut 0

Code: Tout sélectionner

def bottomup(t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[len(keep)-1], b * t[depth] + keep[depth])
        if depth == 1:
            print('failing for ', keep[depth], b*t[depth]+keep[depth])
            print(tmp)

        keep = tmp
        depth -= 1
    return keep
t = [3, 9, 3]
c = [2, 2, 2]
a, b = (2, -5)

print(bottomup(t, c, a, b))
#failing for  6 -39
#[24, 0] <--- on a bien 0 comme attendu
#[9] <--- magic!


6) tu nettoies

Code: Tout sélectionner

def bottomup(t, c, a, b, i=0):
    keep = [0] * len(c)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[k] = max(0 + keep[k], ab * t[depth] + keep[depth])

        tmp[depth] = max(0 + keep[-1], b * t[depth] + keep[depth])

        keep = tmp
        depth -= 1
    return keep
t = [3, 9, 3]
c = [2, 2, 2]
a, b = (2, -5)

print(bottomup(t, c, a, b))



7) tu remarques que si tu appeles ta fonction avec i=1 (pourquoi pas) alors tmp est mal rempli (puisque le premier element est accédé avec k et non 0), donc tu stockes dans tmp correctement

Code: Tout sélectionner

def bottomup(t, c, a, b, i=0):
    keep = [0] * (len(c) -i + 1)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        z = 0
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[z] = max(0 + keep[z], ab * t[depth] + keep[depth-i])
            z += 1

        tmp[-1] = max(0 + keep[-1], b * t[depth] + keep[depth-i])

        keep = tmp
        depth -= 1
    return keep


t = [9, 2, 7, 300, 1]
c = [2, 5, 4, 2, 1]
a, b = 2, -5

print(bottomup(t, c, a, b, 0))
t = [3, 9, 2, 7, 300, 1]
c = [2, 2, 5, 4, 2, 1]
print('next')
print(bottomup(t, c, a, b, 1))



8) enfin, on aurait pu noter que vu que tu avais écrit ta fonction pour le cas i==0, tu pouvais simplement écrire

Code: Tout sélectionner

bottomup0...
    ta fonction sans se préoccuper de i

bottomup(..., i):
    t2 = t[i:]
    c2 = c[i:]
    bottomup0(t2,c2...)


[asse211]

Whaa merci pour les petits détails effectivement c'est toujours plus simples quand on part de "i = 0"

Mais tu na pas répondu à ma question au final ... mdr ^^

En gros je voulais créer un tableau nommé "track[]" qui me permet de stocker une liste d'indice "i" des emplacements qui sont visités pour construire la solution V[i] maximal.

Je sais pas si tu vois ce que je veux dire, mais avec un exemple c'est toujours plus simple :

t = [9, 7, 8, 7, 10, 7]
c = [2, 1, 1, 4, 4, 2]

a, b = -2, 5

Je voudrais obtenir le tableau track suivant : "track[0,1,3,5]" qui sont les indices des cases à visiter pour obtenir V[i] maximum

Merci par avance

[fatal_error]

au lieu de stocker un entier dans tmp/keep, tu stockes une entité
cette entité contient la valeur + les indices visités
quand le max est obtenu par l'opérande de droite, alors tu ajoutes l'indice courant

quelque chose selon les lignes

Code: Tout sélectionner

class Tree:
    def __init__(self, scalar, indices=[]):
        self.scalar = s
        self.indices = indices

    def value():
        return self.scalar

    def indices():
        return self.indices()

def bottomup(t, c, a, b, i=0):
    keep = [Tree(0)] * (len(c) -i + 1)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        z = 0
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            if ab * t[depth] + keep[depth-i].value() > keep[z].value():
                indices = [k] +keep[depth-i].indices()
                max_val = ab * t[depth] + keep[depth-i].value()
            else
                indices =  keep[z].indices()
                max_val = keep[z].value()
            tmp[z] = Tree(max_val, indices)

            z += 1
        #guess what to do..
        tmp[-1] = max(0 + keep[-1], b * t[depth] + keep[depth-i])

        keep = tmp
        depth -= 1
    return keep


[asse211]

[edit]Je ne vois pas très bien ou tu veux en venir ... si on reprend mon algorithme (ne fait pas attention j'ai préféré garder mes indices de base, je mettrais tout ça au propre plus tard ^^)

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=-1):
        track = [0] * len(c)
        for y in range(0, len(c)):
            track[y] = [0, 0]

        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)
            for m in range(0, depth + 1):
                tmp[m] = [0, 0]

            for k in range(i + 1, depth + 1):

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                if depth == 0 and k == 0:
                    tmp[k][0] = ab * t[depth] + track[k][0]
                    tmp[k][1] = k
                else:
                    tmp[k][0] = max(0 + track[k][0], ab * t[depth] + track[depth][0])
                    tmp[k][1] = k

            track = tmp
            depth -= 1

        return track

Comme tu peux le voir, j'utilise le principe de la double dimension. Pour chaque V[i] stocké dans track[] j'ai :

-track[k][0] : V[i]
-track[k][1] : indice de la case dernièrement visité

est-il possible de faire de cette manière, si oui peut-tu essayer de m’expliquer comment je dois mettre à jour "track[k][1]" afin de pouvoir retrouver les indices utilisés pour avoir V[i] ? Je suis désolé d’être long à la détente .. ^^

Merci par avance,

[fatal_error]

ben non tu peux pas faire de cette manière...
a la fin, tu auras track[0][0] et track[0][1]
donc tu ne connaitras qu'un seul 'dernier indice visité'

[asse211]

[édit] il serait possible que tu me face un petit exemple, genre sur 3 valeurs à l'image des schémas que tu avais fait hier soir ? pour que je visualise comment mettre à jour les indices ?

Car ne visualise pas la méthode enfaîte ... c est surtout dans quel cas je dois ajouter l indice à ma liste, et quand je passe donc 0....

Merci par avance

[asse211]

[edit]Slt,

Je me permet de te relancer, après de longue recherche impossible de trouver une manière efficace et sans faille de trouver mes indices parcouru pour obtenir V[i] max... C est frustrant

J'ai cette algo qui ne retourne pas toujours les bons indices parcourus ... :

Code: Tout sélectionner

 def bottomup(self, t, c, a, b, i=-1):
        track = [0] * len(c)
        for y in range(0, len(c)):
            track[y] = [0, []]

        depth = len(c) - 1

        while depth > i:
            tmp = [0] * (depth + 1)
            for m in range(0, depth + 1):
                tmp[m] = [0, []]

            for k in range(i + 1, depth + 1):

                if depth == k:
                    ab = b
                elif c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                if depth == 0 and k == 0:
                    tmp[k][0] = ab * t[depth] + track[k][0]

                else:
                    tmp[k][0] = max(0 + track[k][0], ab * t[depth] + track[depth][0])

                if ab * t[depth] + track[depth][0] > track[k][0]:
                    tmp[k][1] = track[k][1]
                    tmp[k][1].append(depth)
                else:
                    tmp[k][1] = track[k][1]

                print(tmp)

            track = tmp
            depth -= 1

        return track

Merci par avance de ton aide,

[fatal_error]

l'idée est correcte.

pour commencer est-ce que ton algo retourne tjs la bonne somme? (j'en doute?)
et ensuite comme d'hab, petits jeu de test, tu mets des print partout et tu confrontes ce à quoi tu t'attends et ce que tu vois

honnetement, ca m'intéresse pas outre mesure de débugguer _ton_ code (et je pense pas que ca intéresse bcp de monde de débugguer le code des autres), donc commence par mettre des print intéressant, expliquer la valeur observée qui n'est pas celle que tu attendais.
evidemment tu corriges si tu comprends, et si tu comprends pas, tu copies colle l'output, avec ton code permettant de voir l'erreur et tu SPECIFIES ce que tu t'attendais à voir

je t'ai déjà montré un exemple, montres que tu sais faire pareil?

[asse211]

Tout à fait

Avec le code suivant :

https://repl.it/repls/MistyGoldenrodLifecycle

J'obtient bien ma valeur V[i] = 48
Pour l'obtenir on vois facilement qu'il faut passer par tous les indices soit : [0,1,2] pour les positions visitées.



L'algorithme semble donc fonctionner, or si on prend un second exemple toujours à 3 valeurs :

https://repl.it/repls/JitteryFancyLevels

J'obtient bien ma valeur V[i] = 3
Pour l'obtenir on vois facilement qu'il faut passer par les indices soit : [0,1] pour les positions visitées.

Or on obtient avec l'algorithme [1] ... ce qui s'explique assez facilement :

En effet, à l'indice "i = 0" on a besoins de visiter cette case pour maximiser V[i], or il s'agit d'une valeur négative "3 * -5 = -15"

Etant donné que dans mon algorithme j'ajoute les indices visité avec la condition suivante :

Code: Tout sélectionner

if ab * t[depth] + track[depth][0] > track[k][0]:
                tmp[k][1] = track[k][1]
                tmp[k][1].append(depth)
            else:
                tmp[k][1] = track[k][1]

... Obligatoirement pour l'indice "i = 0" l'algorithme passe par le else

Aurait tu une idée de comment je pourrais modifier mon "if .... else ...." afin de capturer l'indice "i = 0" si j'utilise une valeur même négative ?

Merci par avance,

[fatal_error]

d'abord enfin un post bien "construit" au sens où tu montres ce que tu as compris et où tu poses précisément ta question
je sais pas si tu perçois la différence mais c'est bien mieux

Code: Tout sélectionner

Aurait tu une idée de comment je pourrais modifier mon "if .... else ...." afin de capturer l'indice "i = 0" si j'utilise une valeur même négative ?


la réponse la plus bête, et tu la connais, c'est mettre un if depth==0 dans ton else

maintenant ton code a des assertions douteuses:

Code: Tout sélectionner

    if depth == 0 and k == 0:
        tmp[k][0] = ab * t[depth] + track[k][0]


c'est pas toujours qu'il faut prélever le premier caractère
ex:
T=[20,1,6]
C=[2,2,2]
B=-5
A=1
tu maximises avec les indices [1,2] (somme == -5+6=1)

edit: ce qui doit te faire tilter (hormis le passage douteux) c'est: pourquoi je vois ce passage que maintenant. La réponse est simple:
tu as montré que ya un pb dans track[][1]. track[][1] est mis à jour SI tu prélèves qqch.
Les passages où tu prélèves qqch sont les endroits ou ya tmp[][0] ET ab*T[depth]...
donc tu devrais _toujours_ lors d'une ligne où tu assignes tmp[][0] = ab*T[depth].. ; avoir ton tmp[][1] juste en dessous avec l'append à côté
et 2) vu que dans ton if et dans ton else tu as track[][1] = tmp[][1]
autant le factoriser

ton code, toujours incorrect (à cause du if depth == 0 and k == 0) mais plus consistent s'écrit alors

Code: Tout sélectionner


            if depth == 0 and k == 0:
                tmp[k][0] = ab * t[depth] + track[k][0]

            else:
                tmp[k][0] = max(0 + track[k][0], ab * t[depth] + track[depth][0])

            tmp[k][1] = track[k][1]
            if ab * t[depth] + track[depth][0] > track[k][0]:
                tmp[k][1].append(depth)



puis

Code: Tout sélectionner


tmp[k][1] = track[k][1]
if depth == 0 and k == 0:
    tmp[k][0] = ab * t[depth] + track[k][0]
    tmp[k][1].append(0)

else:
    if ab * t[depth] + track[depth][0] > track[k][0]:
        tmp[k][0] = ab * t[depth] + track[depth][0])
        tmp[k][1].append(depth)
    else
        tmp[k][0] = track[depth][0]


[asse211]

Honnêtement je n'ai pas compris tout ton code, il ne retourne absolument plus le bon V[i]

Par contre en utilisant certaines partis j'ai réussi à patcher mon problème du premier indice qui n'était pas prit dans l'exemple suivant :

https://repl.it/repls/InsubstantialBitesizedCookie

L'algorithme trouve bien [0,1]

Pour ce qui est de la partie incohérente dans mon code :

Code: Tout sélectionner

                if depth == k:
                    ab = b

Etant donné que pour le moment je trouve les bonnes valeurs pour mes exemples, je ne vais pas le pacther.

Je veux déjà obtenir mes indices sans failles

Se pose le cas suivant qui pause problème :

https://repl.it/repls/ImpoliteWorrisomeApplicationserver

J'obtiens bien V[i] = 184, aucun soucis Or j'obtiens l'indice "3" dans la liste des indices parcouru.

Je devrais avoir seulement [0,2,4] ...

Je suppose que c'est à cause des 3 symboles "5" qui se suivent

En effet il est plus intéressant de prendre l'indice "2" avec "8 * 10 = 80", mais l'algorithme détecte aussi que si je prends juste le dernier "5" à l'indice "3" avec "8 *4 = 32" je suis aussi plus grand que mon ancienne V[i] ...

Une idée de comment patcher ce cas avec le code que j'ai mis en ligne ?

Merci par avance de ton aide,

[asse211]

Oublie tout ce qu'il y a au dessus !

J'ai clean mon code

Code: Tout sélectionner

    def bottomup(self, t, c, a, b, i=0):
        track = [0] * len(c)
        for y in range(0, len(c)):
            track[y] = [0, []]

        depth = len(c) - 1

        while depth >= i:
            tmp = [0] * (depth - i + 1)
            for m in range(0, depth + 1):
                tmp[m] = [0, []]

            for k in range(i, depth):

                if c[depth] == c[k]:
                    ab = a
                else:
                    ab = b

                tmp[k][1] = track[k][1]

                tmp[k][0] = max(0 + track[k][0], ab * t[depth] + track[depth][0])
               
                if ab * t[depth] + track[depth][0] > track[k][0]:
                    tmp[k][1].append(depth)

            tmp[depth][1] = track[depth][1]
            tmp[depth][0] = max(0 + track[-1][0], b * t[depth] + track[depth][0])

            if b * t[depth] + track[depth][0] > track[-1][0]:
                tmp[depth][1].append(0)

            print(tmp)

            track = tmp
            depth -= 1

        return track

Par contre j'ai à nouveau les mêmes soucis au niveau du stockage des indices ...

Tu aurais une idée pour patcher le problème à mon message juste avant ?

Merci par avance.

[fatal_error]

ca c'est faux

Code: Tout sélectionner

            tmp[depth][1] = track[depth][1]
            tmp[depth][0] = max(0 + track[-1][0], b * t[depth] + track[depth][0])


et si c'est pas faux, c'est à jeter quand même.
SI tu prends la branche de gauche: track[-1][0], alors tu dois stocker tmp[depth][1] = track[-1][1]
SI tu prends la branche de droite: track[depth][0], alors tu dois stocker tmp[depth][1] = track[depth][1]

donc
1) lache ton max qui ne sert à rien. (tu fais en plus le if sur la même chose juste après). non seulement c'est source d'erreur, mais en plus ce n'est même pas performant
2) relis mon poste avec Tree et comprends fortement que tes double arrays ou n'importe quelle autre implem on s'en contrefout, ce qui est important c'est que tu manipules des __entités__. Si tu prends l'entité de gauche, alors tu prends sa valeur ET ses indices. Si tu prends l'entité de droite alors tu prends sa valeur ET ses indices ET tu ajoutes l'indice courant

[asse211]

OK j ai repris ta méthode hors je ne comprends pas ce que tu essaye de faire au niveau de cette ligne :

Code: Tout sélectionner

        #guess what to do..
        tmp[-1] = max(0 + keep[-1], b * t[depth] + keep[depth-i])   

J'ai une erreur qui m interdit d additionner "0" qui est un int avec "keep[-1]" qui est une entity...

Que faut il faire avant afin de pouvoir pallier à ce soucis ?

Merci par avance, bonne soirée à toi

[fatal_error]

Dans ton cas tmp[k] stock un array taille 2 qui represente le couple (valeur, indices). dans mon cas que stocke tmp[k]?

Bonne soiree

[asse211]

Dans ton cas il stocke un objet de la classe Tree avec deux attributs : max_val et indices qui sont accessible via deux méthodes (getter).

Mais ta ligne me retourne des erreurs car je ne peut pas ajouter "0 + un objet"

Pense à dormir... Lol, merci tu est vraiment super sympas de m aider comme ça. J y suis presque je pense ^^

Bonne soirée

[fatal_error]

Dans ce cas la, independamment de lerreur dajouter 0, max doit te retourner...un Tree, et ca na pas lair trop possible. Conclusion: laisse tomber max et ecris la comparaison toi meme

[asse211]

OK je vois ☺️

Je ferrais ça demain !

Bonne soirée

[asse211]

Hey !

Je ne vois pas comment ajouter à la mains à la sortie du for "tmp[-1]" .... C'est un vrai casse tete

Je me tappe des erreurs en veux tu en voila, c'est super difficile de debugger car c'est très abstrait comme exercice.

Si tu à la solution avec un code qui fonctionne je la veut bien, ça doit faire pas loin d'une semaine et 5 jours que je suis sur cette exercice

Sinon je m’arrêterais là, mais ça m’énerve d'échouer sur les indices ...

Merci par avance,

[fatal_error]

https://repl.it/repls/FuchsiaTediousCareware

Code: Tout sélectionner

def bottomup(t, c, a, b, i=0):
    keep = [0] * (len(c) -i + 1)
    depth = len(c) - 1

    while depth >= i:
        tmp = [0] * (depth -i + 1)
        z = 0
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            tmp[z] = max(0 + keep[z], ab * t[depth] + keep[depth-i])
            z += 1

        tmp[-1] = max(0 + keep[-1], b * t[depth] + keep[depth-i])

        keep = tmp
        depth -= 1
    return {"value":keep[0]}

def bottomupWithHistory(t, c, a, b, i=0):
    class History():
        def __init__(self, value=0, indices=[]):
            self.value = value
            self.indices = indices
        def fork(self, value, idx):
            h2 = History(value, [idx])
            h2.value += self.value
            h2.indices += self.indices
            return h2

    keep = [History()] * (len(c) -i + 1)
    depth = len(c) - 1
    while depth >= i:
        tmp = [History()] * (depth -i + 1)
        z = 0
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            if keep[z].value > ab * t[depth] + keep[depth-i].value:
                tmp[z] = keep[z]
            else:
                tmp[z] = keep[depth-i].fork(ab * t[depth], depth)
            z += 1

        if keep[-1].value > b * t[depth] + keep[depth-i].value:
            tmp[z] = keep[-1]
        else:
            tmp[z] = keep[depth-i].fork(b * t[depth], depth)

        keep = tmp
        depth -= 1
    return keep[0]

def bottomupWithDoubleArray(t, c, a, b, i=0):

    keep = [[0,[]]] * (len(c) -i + 1)
    depth = len(c) - 1
    while depth >= i:
        tmp = [[0,[]]] * (depth -i + 1)
        z = 0
        for k in range(i, depth):
            if c[depth] == c[k]:
                ab = a
            else:
                ab = b

            if keep[z][0] > ab * t[depth] + keep[depth-i][0]:
                tmp[z] = keep[z]
            else:
                tmp[z] = [
                    ab * t[depth] + keep[depth-i][0],
                    [depth]+keep[depth-i][1]
                ]
            z += 1

        if keep[-1][0] > b * t[depth] + keep[depth-i][0]:
            tmp[z] = keep[-1]
        else:
            tmp[z] = [
                b * t[depth] + keep[depth-i][0],
                [depth] + keep[depth-i][1]
            ]

        keep = tmp
        depth -= 1
    return {'value':keep[0][0], 'indices':keep[0][1]}

def test(t,c,a,b,expect,i=0):
    res=bottomup(t, c, a, b, i)
    if expect != res['value']:
        print('got ', expect, res)
        raise Exception('fkk')

    res=bottomupWithHistory(t, c, a, b, i)
    if expect != res.value:
        print('got ', expect, res)
        raise Exception('fkk')
    print(res.indices)

    res=bottomupWithDoubleArray(t, c, a, b, i)
    if expect != res['value']:
        print('got ', expect, res)
        raise Exception('fkk')
    print(res['indices'])

test(t=[9, 2, 7, 300, 1],
     c=[2, 5, 4, 2, 1],
     a=2,b=-5,
     expect=555)

#work with i offsets
test(
    t = [3, 9, 2, 7, 300, 1],
    c = [2, 2, 5, 4, 2, 1],
    a=2,b=-5,
    expect=555,i=1)

#standard example
test(
    t = (9,7,8,7,10,7),
    c = (2,1,1,4,4,2),
    a=-2,b=5,
    expect=170)

#skips first elem to maximize sum
test(
    t = (9,2,6),
    c = (1,1,1),
    a=2,b=-5,
    expect=2)

#skips intermediate elems to maximize sum
test(
    t = (1,2,1,1,1,1),
    c = (1,1,2,2,1,1),
    a=1,b=-1,
    expect=3)


au delà des problèmes d'algorithmie, je te suggère _grandement_ de t'entrainer à programmer sur des problèmes plus simples.
ne pas savoir transformer un max en if/else est assez pénalisant

tu as la solution telle quelle, mais débugguer un programme fait partie de 50% sinon plus du travail, donc même si tu as compris c'est crucial de t'entrainer à débugguer sinon tu pourras jamais corriger tes algo...