Pokročilé techniky dynamického programování

[zapotocnylubos]

Digit DP

Počítání čísel v rozsahu [L, R] splňujících zadanou podmínku.

• Počet čísel dělitelných K
• Počet čísel bez opakující se cifry
• Počet čísel s daným digit sumem

Interval DP

Řešení úloh na podintervalech pole nebo řetězce.

• Matrix chain multiplication
• Burst balloons
• Optimal BST
• Palindrome partitioning

Tree DP

DP na stromech, stav se propaguje přes vrcholy.

• Maximální nezávislá množina na stromě
• Průměr stromu
• Rerooting – přepočet výsledku pro každý kořen

Bitmask DP

DP přes podmnožiny prvků (nad rámec TSP).

• Covering problems – pokrytí množiny podmnožinami
• Assignment problem
• Hamiltonova cesta s omezeními

SOS DP (Sum over Subsets)

Rychlý výpočet součtů přes všechny podmnožiny.

• AND/OR konvoluce
• Počet dvojic s daným AND/OR/XOR

Convex Hull Trick

Optimalizace DP přechodů s lineárními funkcemi.

• Divide the cities
• Minimum cost to cut a stick

Divide & Conquer DP

Optimalizace DP kde optimální dělení je monotónní.

• Optimal k-segmentové rozdělení pole
• Yao's speedup

Profile DP

Řešení úloh po řádcích nebo sloupcích, stav = "profil" hranice.

• Pokládání dlaždic (dominoes, trominoes)
• Broken profile DP