De ce contează?
Imaginează-ți o firmă cu organigrama în formă de arbore: fiecare șef are echipa lui, iar fiecare membru poate avea la rândul lui o subechipă. Vrei să răspunzi la o întrebare („câți oameni intră în proiect?”) pentru fiecare șef. Nu poți răspunde pentru un șef până nu primești răspunsul de la toate subechipele lui. Așa că începi de la cei fără subalterni — frunzele — și urci spre vârf: fiecare nod își combină rezultatele copiilor într-un singur număr. Exact asta face DP pe arbori.
Intuiția
Pe un arbore, fiecare nod „stăpânește” un subarbore — el plus tot ce atârnă sub el. Cheia e că acel subarbore nu depinde de restul arborelui: e o lume închisă, o subproblemă completă de sine stătătoare. Dacă știi răspunsul pentru subarborii copiilor, răspunsul pentru nod se obține combinându-le.
Spre deosebire de DP-ul pe șiruri, aici subproblemele nu se suprapun: subarborii a doi frați sunt lumi complet separate. De aceea nu ai nevoie de nicio memoizare specială — un DFS în post-ordine (întâi copiii, apoi părintele) ESTE exact ordinea de calcul a DP-ului: frunzele primele, rădăcina ultima.