DP na LeetCode: 3 úlohy s rekurentními vztahy

Dynamické programování: intuitivní přístup ke třem úlohám LeetCode

Dynamické programování (DP) umožňuje řešit úlohy počítání cest a optimalizace pomocí rekurentních vztahů. Podíváme se na úlohy 62 (Unique Paths), 64 (Minimum Path Sum) a 70 (Climbing Stairs). Každá z nich demonstruje klíčové znaky DP: optimální podstrukturu a překrývající se podúlohy.

Unique Paths: počítání tras na mřížce

Robot se pohybuje po mřížce m × n z (0,0) do (m-1,n-1), přičemž se smí pohybovat pouze doprava nebo dolů. Je třeba najít počet unikátních cest.

Každá cesta se skládá z (m-1) kroků dolů a (n-1) kroků doprava. Kombinatorické řešení využívá binomický koeficient C(m+n-2, m-1). Na pohovoru se však vyžaduje algoritmický přístup.

Definujeme dp[i][j] jako počet cest do buňky (i,j). Rekurentní vztah:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Okrajové podmínky:

• dp[0][j] = 1 (první řádek)
• dp[i][0] = 1 (první sloupec)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Časová složitost O(m·n). Řešení využívá pravidlo sčítání pro disjunktní množiny cest.

Minimum Path Sum: minimalizace ceny cesty

Je dána mřížka m × n s nezápornými čísly. Najít minimální součet hodnot na cestě z (0,0) do (m-1,n-1) při pohybu doprava nebo dolů.

Hladový algoritmus (výběr lokálního minima) nefunguje – vede do slepé uličky s vysokými hodnotami. Je třeba globální optimalizace.

Definujeme dp[i][j] jako minimální cenu cesty do (i,j). Rekurentní vztah:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Okrajové podmínky:

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

Složitost O(m·n). Každá hodnota se používá pro všechny následující buňky.

Climbing Stairs: Fibonacciho čísla v DP

Výstup po schodech s n stupni (1 ≤ n ≤ 45), každý krok – 1 nebo 2 stupně. Najít počet způsobů.

Pro n=1: 1 způsob

n=2: 2 způsoby (1+1, 2)

n=3: 3 způsoby (1+1+1, 1+2, 2+1)

Rekurentní vztah:

dp[n] = dp[n-1] + dp[n-2]

Jednoduchá rekurze vede k exponenciální složitosti O(φ^n) kvůli opakovaným výpočtům. Pole DP problém řeší:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Optimalizovaná verze využívá O(1) paměti se dvěma proměnnými.

Znaky úloh na dynamické programování

Aplikujte DP při splnění dvou podmínek:

• Optimální podstruktura: optimální řešení se skládá z optimálních řešení podúloh.
• Překrývající se podúlohy: stejné podúlohy se počítají opakovaně.

| Úloha | Optimální podstruktura | Překrývající se podúlohy |

|--------|-------------------------|---------------------------|

| Unique Paths | Součet cest ze sousedních buněk | Každá cesta do buňky se překrývá |

| Min Path Sum | Min. cena ze sousedů | Cena se používá pro všechny níže/vpravo |

| Climbing Stairs | Součet z n-1 a n-2 | Rekurzivní volání se opakují |

Co je důležité

• Rekurentní vztahy určují podstatu DP: dp[i][j] závisí pouze na sousedních již vypočtených hodnotách.
• Okrajové podmínky se vyplňují zvlášť pro první řádek/sloupec nebo základní případy.
• Časová složitost je vždy O(velikost vstupu) při správné tabulkové implementaci.
• Paměť lze optimalizovat: pro mřížky – jeden řádek, pro lineární úlohy – dvě proměnné.
• Kombinatorika často nabízí matematický zkrat, ale algoritmické řešení je důležitější pro pohovory.

— Editorial Team