Programowanie dynamiczne na LeetCode: 3 zadania z formułami rekurencyjnymi

Programowanie dynamiczne: intuicyjne podejście do trzech zadań LeetCode

Programowanie dynamiczne (PD) pozwala rozwiązywać zadania liczenia ścieżek i optymalizacji za pomocą relacji rekurencyjnych. Omówimy zadania 62 (Unique Paths), 64 (Minimum Path Sum) i 70 (Climbing Stairs). Każde z nich pokazuje kluczowe cechy PD: optymalną podstrukturę i nakładające się podproblemy.

Unique Paths: liczenie tras na siatce

Robot porusza się po siatce m × n z (0,0) do (m-1,n-1), przemieszczając się tylko w prawo lub w dół. Należy znaleźć liczbę unikalnych ścieżek.

Każda ścieżka składa się z (m-1) kroków w dół i (n-1) kroków w prawo. Rozwiązanie kombinatoryczne wykorzystuje współczynnik dwumianowy C(m+n-2, m-1). Jednak na rozmowie kwalifikacyjnej wymagane jest podejście algorytmiczne.

Definiujemy dp[i][j] jako liczbę ścieżek do komórki (i,j). Relacja rekurencyjna:

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

Warunki brzegowe:

• dp[0][j] = 1 (pierwszy wiersz)
• dp[i][0] = 1 (pierwsza kolumna)

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]

Złożoność czasowa O(m·n). Rozwiązanie wykorzystuje zasadę dodawania dla rozłącznych zbiorów ścieżek.

Minimum Path Sum: minimalizacja kosztu ścieżki

Dana jest siatka m × n z nieujemnymi liczbami. Znaleźć minimalną sumę wartości na ścieżce z (0,0) do (m-1,n-1) przy ruchu w prawo lub w dół.

Algorytm zachłanny (wybór lokalnego minimum) nie działa — prowadzi do ślepego zaułka z wysokimi wartościami. Wymagana jest optymalizacja globalna.

Definiujemy dp[i][j] jako minimalny koszt ścieżki do (i,j). Relacja rekurencyjna:

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

Warunki brzegowe:

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]

Złożoność O(m·n). Każda wartość jest wykorzystywana dla wszystkich kolejnych komórek.

Climbing Stairs: liczby Fibonacciego w PD

Wchodzenie po schodach z n stopniami (1 ≤ n ≤ 45), każdy krok to 1 lub 2 stopnie. Znaleźć liczbę sposobów.

Dla n=1: 1 sposób

n=2: 2 sposoby (1+1, 2)

n=3: 3 sposoby (1+1+1, 1+2, 2+1)

Relacja rekurencyjna:

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

Prosta rekurencja prowadzi do złożoności wykładniczej O(φ^n) z powodu powtarzających się obliczeń. Tablica PD rozwiązuje problem:

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]

Zoptymalizowana wersja wykorzystuje O(1) pamięci z dwiema zmiennymi.

Cechy zadań na programowanie dynamiczne

Stosuj PD przy spełnieniu dwóch warunków:

• Optymalna podstruktura: optymalne rozwiązanie składa się z optymalnych rozwiązań podproblemów.
• Nakładające się podproblemy: te same podproblemy są obliczane wielokrotnie.

| Zadanie | Optymalna podstruktura | Nakładające się podproblemy |

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

| Unique Paths | Suma ścieżek z sąsiednich komórek | Każda ścieżka do komórki nakłada się |

| Min Path Sum | Min. koszt z sąsiadów | Koszt jest wykorzystywany dla wszystkich poniżej/po prawej |

| Climbing Stairs | Suma z n-1 i n-2 | Wywołania rekurencyjne się powtarzają |

Co jest ważne

• Relacje rekurencyjne definiują istotę PD: dp[i][j] zależy tylko od sąsiednich już obliczonych wartości.
• Warunki brzegowe są wypełniane osobno dla pierwszego wiersza/kolumny lub przypadków bazowych.
• Złożoność czasowa zawsze O(rozmiar wejścia) przy poprawnej implementacji tabelarycznej.
• Pamięć można zoptymalizować: dla siatek — jeden wiersz, dla zadań liniowych — dwie zmienne.
• Kombinatoryka często daje matematyczny skrót, ale rozwiązanie algorytmiczne jest ważniejsze na rozmowach kwalifikacyjnych.

— Editorial Team