El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Programació Dinàmica

Següent ►
►

El tancament de la lliçó anterior va deixar una pregunta oberta: què fem quan un problema té subestructura òptima però l'aposta voraç falla — quan pagar 6 € exigeix adonar-se que 3+3 guanya a començar pel 4? La resposta és la programació dinàmica (PD): en lloc de jugar-s'ho tot a una decisió, es consideren totes les decisions possibles... però sense pagar el preu exponencial de la força bruta, perquè els subproblemes repetits es calculen una sola vegada i es guarden. És exactament la idea que vam apuntar a 02-02 amb construeix_index — gastar memòria per no repetir feina — elevada a estratègia de disseny. En aquesta lliçó la desenvoluparem en els seus dos sabors (memoïtzació i tabulació), l'aplicarem a dos problemes de RutaBus — el trajecte més barat amb tarifes per trams i la selecció de millores de flota amb pressupost limitat — i aprendrem no només a calcular el valor òptim, sinó a reconstruir la solució que l'assoleix.

Contingut

  1. Els dos ingredients: subproblemes solapats i subestructura òptima
  2. Fibonacci: l'exemple mínim del desastre i la seva cura
  3. Memoïtzació (top-down): recordar allò ja calculat
  4. Problema RutaBus: el trajecte més barat amb tarifes per trams
  5. Tabulació (bottom-up): omplir la taula sense recursió
  6. Top-down vs bottom-up
  7. La motxilla 0/1: millores de flota amb pressupost limitat
  8. Reconstruir la solució, no només el valor

Els dos ingredients: subproblemes solapats i subestructura òptima

La programació dinàmica s'aplica quan el problema té, alhora:

  • Subestructura òptima: la solució òptima del problema es construeix a partir de solucions òptimes dels seus subproblemes. (La mateixa propietat que exigia greedy a 03-02 — no és casualitat: greedy és, en certa manera, una PD que s'atreveix a explorar una sola branca.)
  • Subproblemes solapats: en descompondre el problema, els mateixos subproblemes apareixen una vegada i una altra. Aquí hi ha la diferència clau amb divideix i venceràs (03-01), els subproblemes del qual eren independents: si no hi ha solapament, guardar resultats no estalvia res.
Estratègia Subestructura òptima Subproblemes Decisions explorades
Divideix i venceràs (no necessàriament d'optimització) Independents —
Greedy Sí L'un rere l'altre Una (la voraç)
Programació dinàmica Sí Solapats Totes (guardant resultats)

Fibonacci: l'exemple mínim del desastre i la seva cura

Abans de pujar a l'autobús, l'exemple més petit possible de subproblemes solapats: la successió de Fibonacci (1, 1, 2, 3, 5, 8, ...), on cada terme és la suma dels dos anteriors.

def fib(n):
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)

A 02-01 vam aprendre a analitzar recursives comptant crides. Comptem-les: fib(5) crida fib(4) i fib(3); fib(4) crida fib(3) — una altra vegada! — i fib(2)...

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3) (repetit!)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]

fib(3) es calcula 2 vegades aquí; a fib(50), fib(3) es calcularia milers de milions de vegades. L'arbre de crides creix com O(2ⁿ) — la pitjor categoria de la jerarquia de 01-03 — per a un problema que només té n subproblemes diferents: fib(1), fib(2), ..., fib(n). Tot l'excés és feina repetida. La cura: calcular cadascun una vegada i apuntar-lo.

Memoïtzació (top-down): recordar allò ja calculat

Memoïtzació = embolcallar la recursió amb una "llibreta" (normalment un diccionari) on s'anota cada resultat la primera vegada que es calcula; les vegades següents es retorna l'anotació en O(1) — la consulta a diccionari el cost de la qual vam estudiar amb construeix_index a 02-02.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:               # ja ho hem calculat? -> O(1)
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Anàlisi amb les eines del Mòdul 2:

  • Temps: cada fib_memo(k) es calcula de debò una sola vegada (després queda al memo). Hi ha n subproblemes i cadascun fa feina O(1) fora de les recursions: O(n). D'exponencial a lineal.
  • Espai: el diccionari guarda n entrades i la pila de recursió arriba a profunditat n (02-02): O(n).

Aquest és, amb nom i cognoms, el trade-off temps ↔ espai que vam anticipar a 02-02: paguem O(n) de memòria per fer caure en picat el temps de O(2ⁿ) a O(n). Poques vegades en informàtica es compra tant amb tan poc.

Nota pràctica: Python porta la memoïtzació de sèrie amb from functools import lru_cache i el decorador @lru_cache(maxsize=None) sobre la funció recursiva. Fes-lo servir en producció; aquí escrivim la llibreta a mà per veure el mecanisme.

Problema RutaBus: el trajecte més barat amb tarifes per trams

Ara un problema real de RutaBus. A la línia L2 hi ha n + 1 parades numerades de 0 (Plaça Major) a n (Parc del Riu). Des de cada parada i el passatger pot:

  • avançar 1 parada pagant tarifa1[i] cèntims, o
  • avançar 2 parades (servei semidirecte) pagant tarifa2[i] cèntims.

Quin és el cost mínim per anar de la parada 0 a la parada n?

# Exemple amb n = 5 (parades 0..5)
tarifa1 = [120, 140, 100, 130, 110]   # tarifa1[i]: de i a i+1
tarifa2 = [210, 220, 260, 180]        # tarifa2[i]: de i a i+2

Pas 1 — definir el subproblema. Sigui cost(i) = cost mínim per arribar de la parada i fins a la n. Volem cost(0).

Pas 2 — la recurrència (subestructura òptima). Des d'i només hi ha dues primeres decisions possibles; el que vingui després ha de ser, al seu torn, òptim:

cost(n)   = 0                                  (ja hem arribat)
cost(n-1) = tarifa1[n-1]                       (només hi cap el salt d'1)
cost(i)   = min(tarifa1[i] + cost(i+1),
                tarifa2[i] + cost(i+2))

Pas 3 — comprovar el solapament. cost(3) el necessiten tant cost(2) (saltant 1) com cost(1) (saltant 2): els mateixos subproblemes apareixen per camins diferents, igual que a Fibonacci. Sense memòria, la recursió seria exponencial; amb memòria, només hi ha n + 1 subproblemes.

Versió top-down (memoïtzació):

def cost_minim_memo(tarifa1, tarifa2, i=0, memo=None):
    n = len(tarifa1)                    # nre. de trams = nre. de parades - 1
    if memo is None:
        memo = {}
    if i in memo:
        return memo[i]
    if i == n:                          # cas base: hem arribat
        return 0
    if i == n - 1:                      # penúltima parada: només salt d'1
        return tarifa1[i]

    saltar1 = tarifa1[i] + cost_minim_memo(tarifa1, tarifa2, i + 1, memo)
    saltar2 = tarifa2[i] + cost_minim_memo(tarifa1, tarifa2, i + 2, memo)
    memo[i] = min(saltar1, saltar2)
    return memo[i]

print(cost_minim_memo(tarifa1, tarifa2))   # 490

Temps O(n) — cada parada es resol una sola vegada — i espai O(n) entre el memo i la pila de recursió.

Tabulació (bottom-up): omplir la taula sense recursió

La tabulació capgira el càlcul: en lloc de partir de la pregunta grossa i baixar (top-down), parteix dels casos base i puja, omplint una taula amb un bucle. Sense recursió, sense pila.

def cost_minim_tab(tarifa1, tarifa2):
    n = len(tarifa1)
    cost = [0] * (n + 1)                # cost[i]: mínim des de i fins a n
    cost[n] = 0                         # casos base
    cost[n - 1] = tarifa1[n - 1]

    for i in range(n - 2, -1, -1):      # de la parada n-2 cap a la 0
        cost[i] = min(tarifa1[i] + cost[i + 1],
                      tarifa2[i] + cost[i + 2])
    return cost

print(cost_minim_tab(tarifa1, tarifa2))
# [490, 400, 280, 180, 110, 0]

Omplim la taula a mà, cel·la a cel·la i en el mateix ordre que el bucle — verificar dues o tres cel·les manualment és la prova unitària més barata que existeix per a una PD:

i càlcul cost[i]
5 cas base (destinació) 0
4 cas base: tarifa1[4] = 110 110
3 min(tarifa1[3]+cost[4], tarifa2[3]+cost[5]) = min(130+110, 180+0) = min(240, 180) 180
2 min(100+cost[3], 260+cost[4]) = min(100+180, 260+110) = min(280, 370) 280
1 min(140+cost[2], 220+cost[3]) = min(140+280, 220+180) = min(420, 400) 400
0 min(120+cost[1], 210+cost[2]) = min(120+520... compte, cost[1] és 400!) = min(120+400, 210+280) = min(520, 490) 490

El cost mínim és de 490 cèntims. Observa la cel·la i = 3: allà el semidirecte (180) guanya al salt simple (240); en canvi a i = 2 convé el salt simple. La taula pren, per a cada parada, la millor decisió — res d'apostes irrevocables.

Temps O(n), espai O(n) per a la taula — i fixa-t'hi: com que cost[i] només consulta i+1 i i+2, n'hi hauria prou amb dues variables, abaixant l'espai auxiliar a O(1). Aquesta mena de reduccions de memòria s'estudia al Mòdul 5 (05-02); aquí en tenim prou de saber que existeix.

Top-down vs bottom-up

Aspecte Memoïtzació (top-down) Tabulació (bottom-up)
Forma Recursió + diccionari Bucles + taula (llista/matriu)
Ordre de càlcul El que dicti la recursió Explícit, dels casos base cap amunt
Subproblemes calculats Només els realment necessaris Tots els de la taula
Pila de recursió Sí — risc de RecursionError amb n gran (02-02) No
Facilitat d'escriptura Gairebé directa des de la recurrència Exigeix pensar l'ordre d'ompliment
Optimitzar espai Difícil Fàcil (quedar-se amb les últimes files)

Regla pràctica: dissenya sempre primer la recurrència (és el cor de la PD); després escriu la memoïtzació per validar-la ràpid, i passa-la a tabulació si necessites rendiment, control de l'espai o evitar la pila.

La motxilla 0/1: millores de flota amb pressupost limitat

El problema estrella de la PD, en versió RutaBus. La direcció aprova un pressupost de 9 (milers d'euros) i l'equip tècnic proposa quatre millores, cadascuna amb el seu cost i el seu benefici estimat (índex de millora de servei):

millores = [
    ("Wifi a bord",           2, 3),    # (nom, cost, benefici)
    ("Rampa accessibilitat",  3, 4),
    ("Panells informació",    4, 5),
    ("Climatització eco",     5, 8),
]
PRESSUPOST = 9

Cada millora es finança sencera o no es finança (d'aquí ve el "0/1": res de mig wifi). Objectiu: maximitzar el benefici total sense excedir el pressupost. El greedy per ràtio benefici/cost falla en general (és el canvi de monedes una altra vegada); la PD ho resol de forma exacta.

Subproblema: V[i][p] = benefici màxim usant només les i primeres millores amb pressupost p.

Recurrència: per a la millora i-èsima, de cost c i benefici b:

V[i][p] = V[i-1][p]                          si c > p   (no hi cap)
V[i][p] = max(V[i-1][p],                     (opció A: no finançar-la)
              V[i-1][p-c] + b)               (opció B: finançar-la)
def motxilla_millores(millores, pressupost):
    n = len(millores)
    # taula (n+1) x (pressupost+1) inicialitzada a 0 (fila 0 = sense millores)
    V = [[0] * (pressupost + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        nom, c, b = millores[i - 1]
        for p in range(pressupost + 1):
            if c > p:                                   # no hi cap
                V[i][p] = V[i - 1][p]
            else:
                V[i][p] = max(V[i - 1][p],              # sense la millora i
                              V[i - 1][p - c] + b)      # amb la millora i
    return V

V = motxilla_millores(millores, PRESSUPOST)
print(V[len(millores)][PRESSUPOST])   # 13

La taula completa (files: millores considerades fins al moment; columnes: pressupost 0..9):

p=0 1 2 3 4 5 6 7 8 9
∅ (sense millores) 0 0 0 0 0 0 0 0 0 0
+Wifi (2, 3) 0 0 3 3 3 3 3 3 3 3
+Rampa (3, 4) 0 0 3 4 4 7 7 7 7 7
+Panells (4, 5) 0 0 3 4 5 7 8 9 9 12
+Clima (5, 8) 0 0 3 4 5 8 8 11 12 13

Llegim diverses cel·les per entendre el mecanisme — això és el que converteix la taula en coneixement:

  • Fila Wifi, p=2: per fi hi cap el wifi (cost 2): max(V[∅][2], V[∅][0] + 3) = max(0, 3) = 3. Tota la fila val 3 d'aquí en endavant: amb una sola millora disponible no hi ha res més a gratar.
  • Fila Rampa, p=3: max(V[wifi][3], V[wifi][0] + 4) = max(3, 4) = 4. Amb pressupost 3 convé la rampa sola abans que el wifi sol.
  • Fila Rampa, p=5: max(V[wifi][5], V[wifi][5−3] + 4) = max(3, 3 + 4) = 7. Finançar la rampa compensa perquè amb el pressupost restant (2) encara hi cap el wifi: la cel·la V[wifi][2] = 3 ja contenia aquesta millor decisió prèvia. Cada cel·la reutilitza òptims ja calculats: subestructura òptima en acció.
  • Fila Panells, p=9: max(V[rampa][9], V[rampa][9−4] + 5) = max(7, 7 + 5) = 12. Finançant els panells (4) en queden 5, i V[rampa][5] = 7 era "wifi + rampa": total wifi + rampa + panells = 12.
  • Fila Clima, p=9 — la resposta final: max(V[panells][9], V[panells][9−5] + 8) = max(12, 5 + 8) = 13. Finançar la climatització deixa pressupost 4, l'òptim previ del qual era V[panells][4] = 5 (els panells sols). El màxim global és 13.

Cost de l'algorisme: dos bucles imbricats → O(n · P) en temps i espai (n millores, P pressupost), una anàlisi directa amb les regles de 02-01. Nota fina: aquest cost depèn del valor numèric P, no només de quants elements hi ha — la motxilla per PD és eficient per a pressupostos moderats, no gratuïta en general.

Reconstruir la solució, no només el valor

"El benefici màxim és 13" no li serveix a la direcció: vol saber quines millores finançar. La taula ja conté aquesta informació — n'hi ha prou de recórrer-la cap enrere preguntant a cada fila "aquesta millora va canviar el valor?":

def reconstrueix(millores, V, pressupost):
    seleccio = []
    p = pressupost
    for i in range(len(millores), 0, -1):    # de l'última fila a la primera
        if V[i][p] != V[i - 1][p]:           # la millora i va ser decisiva
            nom, c, b = millores[i - 1]
            seleccio.append(nom)
            p -= c                           # en descomptem el cost
    return list(reversed(seleccio))

print(reconstrueix(millores, V, PRESSUPOST))
# ['Panells informació', 'Climatització eco']

Traça sobre la taula anterior:

  1. Fila Clima, p=9: V[4][9] = 13 ≠ V[3][9] = 12 → la climatització entra; pressupost restant: 9 − 5 = 4.
  2. Fila Panells, p=4: V[3][4] = 5 ≠ V[2][4] = 4 → els panells entren; restant: 4 − 4 = 0.
  3. Fila Rampa, p=0: V[2][0] = 0 = V[1][0] → la rampa no va canviar res: fora.
  4. Fila Wifi, p=0: V[1][0] = 0 = V[0][0] → fora.

Selecció òptima: panells + climatització (cost 4 + 5 = 9, benefici 5 + 8 = 13). Fixa't en el detall antiintuïtiu: el wifi, la millora amb millor ràtio benefici/cost (1,5), no és a l'òptim — un greedy per ràtio l'hauria pres primer i hauria quedat atrapat. La PD ho va veure venir perquè va explorar totes les combinacions... pagant cada subproblema una sola vegada.

El mateix truc de "mirar de quina cel·la vinc" reconstrueix el trajecte barat de la L2: a cada parada i, si cost[i] == tarifa1[i] + cost[i+1] l'òptim va saltar 1 parada; si no, en va saltar 2. Amb la nostra taula: 0 →(210)→ 2 →(100)→ 3 →(180)→ 5, total 490.

Tanquem amb la menció promesa: la PD també opera sobre grafs complets — Floyd-Warshall calcula els camins mínims entre tots els parells de parades de la xarxa RutaBus omplint una taula de subproblemes indexada per parelles de parades i nodes intermedis permesos. És PD pura sobre grafs i l'estudiarem a 04-06.

Errors Comuns i Consells

  • Començar a programar sense escriure la recurrència. La PD es dissenya en paper: subproblema (què significa exactament V[i][p]?), recurrència, casos base. El codi és la traducció literal; sense recurrència clara, en sortirà un garbuix d'índexs.
  • Definir malament el subproblema. Si no pots expressar la recurrència usant només subproblemes "més petits", la definició no serveix. Reformula-la — sovint afegint un paràmetre, com el "usant només les i primeres millores" de la motxilla.
  • No verificar cel·les a mà. Tria 2-3 cel·les de la taula, recalcula-les amb la recurrència i converteix-les en assert de test. Els errors d'índexs (i vs i-1, p vs p-c) són silenciosos i aquesta és la xarxa que els caça.
  • Oblidar els casos base o deixar la taula sense inicialitzar. cost[n] = 0 i la fila ∅ de la motxilla no són decoració: tota la taula s'hi recolza.
  • Usar memoïtzació amb llistes com a clau. Les claus d'un diccionari han de ser immutables (int, tuple); una llista llança TypeError. Converteix l'estat a tupla.
  • Recursió massa profunda. Per a n de desenes de milers, la memoïtzació esgota la pila de Python (02-02): passa a tabulació.
  • Aplicar PD on no hi ha solapament. Si cada subproblema apareix una sola vegada, el memo no estalvia res i només gasta memòria: això és divideix i venceràs (03-01) i no necessita llibreta.

Exercicis

Exercici 1

Un passatger a la parada 0 pot avançar 1 o 2 parades a cada pas (sense tarifes: aquí només comptem camins). Escriu maneres_arribar(n) que compti de quantes maneres diferents pot arribar exactament a la parada n, amb memoïtzació. Calcula a mà els valors per a n = 1..5 i observa quina successió apareix. Quin és el cost temporal i espacial?

Exercici 2

Converteix maneres_arribar a tabulació i redueix-ne després l'espai auxiliar a O(1) conservant el temps O(n). (Pista: quantes cel·les anteriors necessita cada cel·la?)

Exercici 3

Al problema de les millores de flota s'hi afegeix una cinquena opció: ("GPS de flota", 4, 6). Amb pressupost 9, calcula la nova fila de la taula i reconstrueix la selecció òptima. Continua sent-hi la climatització? I els panells?

Solucions

Solució 1

def maneres_arribar(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 1        # una única manera: el camí buit
    if n == 1:
        return 1        # només un salt d'1
    memo[n] = maneres_arribar(n - 1, memo) + maneres_arribar(n - 2, memo)
    return memo[n]

Per arribar a n, l'últim salt va venir de n−1 o de n−2, i tots dos conjunts de camins són disjunts: f(n) = f(n−1) + f(n−2). Valors: f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8 — Fibonacci desplaçat. El nostre problema de transport amaga la mateixa estructura que l'exemple "de joguina": reconèixer recurrències conegudes sota disfresses noves és una de les grans destreses de la PD. Temps O(n), espai O(n).

Solució 2

def maneres_arribar_tab(n):
    if n <= 1:
        return 1
    anterior2, anterior1 = 1, 1          # f(0), f(1)
    for _ in range(2, n + 1):
        anterior2, anterior1 = anterior1, anterior1 + anterior2
    return anterior1

Cada cel·la només necessita les dues anteriors, així que la "taula" es comprimeix en dues variables: temps O(n), espai auxiliar O(1) i sense pila de recursió. És el trade-off temps↔espai de 02-02 ajustat al mínim imprescindible.

Solució 3

La nova fila es calcula amb V[5][p] = max(V[4][p], V[4][p−4] + 6) per a p ≥ 4. A la cel·la final: V[5][9] = max(V[4][9], V[4][5] + 6) = max(13, 8 + 6) = 14. Reconstrucció: V[5][9] = 14 ≠ V[4][9] = 13 → el GPS entra, restant 5; V[4][5] = 8 ≠ V[3][5] = 7 → la climatització entra, restant 0; no hi cap res més. Selecció òptima: GPS + climatització (cost 4 + 5 = 9, benefici 14). La climatització continua, però els panells surten: afegir un candidat pot reorganitzar tota la solució — exactament el que un greedy de decisions irrevocables mai no podria fer.

Conclusió

La programació dinàmica és l'estratègia per a problemes amb subestructura òptima i subproblemes solapats: s'explora l'espai complet de decisions, però cada subproblema es paga una sola vegada, canviant memòria per temps — el trade-off que veníem anunciant des de 02-02, ara amb nom propi. Hem après el seu mètode de disseny (definir el subproblema → escriure la recurrència → fixar els casos base), les seves dues realitzacions — memoïtzació top-down i tabulació bottom-up —, i l'hem aplicada al trajecte més barat de la L2 (490 cèntims, i sabem per on) i a la motxilla 0/1 de les millores de flota, incloent-hi la reconstrucció de la solució recorrent la taula cap enrere. Amb divideix i venceràs, greedy i PD ja tenim tres maneres de construir solucions; ens falta l'estratègia per a quan no queda més remei que buscar: problemes de restriccions on cal provar combinacions, detectar carrerons sense sortida i tornar sobre els propis passos. Aquesta exploració sistemàtica amb marxa enrere — el backtracking — tanca el mòdul a la propera lliçó, on a més posarem les quatre estratègies cara a cara.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats