MidПрактика12 min

Классические задачи DP

Fibonacci, Climbing Stairs, Coin Change, House Robber и другие

AlgoDynamic programming

Задача 1: Coin Change

Условие: минимальное количество монет для суммы amount.

<?php
declare(strict_types=1);

/**
 * @param list<int> $coins
 */
function coinChange(array $coins, int $amount): int
{
    $dp = array_fill(0, $amount + 1, $amount + 1);
    $dp[0] = 0;

    for ($i = 1; $i <= $amount; $i++) {
        foreach ($coins as $coin) {
            if ($coin <= $i && $dp[$i - $coin] + 1 < $dp[$i]) {
                $dp[$i] = $dp[$i - $coin] + 1;
            }
        }
    }

    return $dp[$amount] > $amount ? -1 : $dp[$amount];
}

// coins = [1, 5, 11], amount = 15
// dp[0]=0
// dp[1]=1 (1)
// dp[5]=1 (5)
// dp[10]=2 (5+5)
// dp[11]=1 (11)
// dp[15]=3 (5+5+5) — not 15/11=1+4*1=5 coins!
## Задача 2: House Robber

Условие: нельзя грабить два соседних дома. Максимальная сумма?

<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 */
function rob(array $nums): int
{
    if ($nums === []) {
        return 0;
    }
    if (count($nums) === 1) {
        return $nums[0];
    }

    $prev2 = 0;          // dp[i-2]
    $prev1 = $nums[0];   // dp[i-1]

    for ($i = 1; $i < count($nums); $i++) {
        $curr = max($prev1, $prev2 + $nums[$i]);
        $prev2 = $prev1;
        $prev1 = $curr;
    }

    return $prev1;
}

// nums = [2, 7, 9, 3, 1]
// i=0: prev1=2
// i=1: curr=max(2, 0+7)=7
// i=2: curr=max(7, 2+9)=11
// i=3: curr=max(11, 7+3)=11
// i=4: curr=max(11, 11+1)=12
// Answer: 12 (houses 2, 9, 1)
## Задача 3: Longest Increasing Subsequence (LIS) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 */
function lengthOfLis(array $nums): int
{
    $n = count($nums);
    $dp = array_fill(0, $n, 1); // dp[i] = length of LIS ending at nums[i]

    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($nums[$j] < $nums[$i]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }

    return max($dp);
}

// nums = [10, 9, 2, 5, 3, 7, 101, 18]
// dp  = [1, 1, 1, 2, 2, 3,  4,   4]
// LIS: [2, 3, 7, 101] or [2, 5, 7, 101], length 4
O(n log n) версия с бинарным поиском: 
<?php
declare(strict_types=1);

/**
 * O(n log n) version with binary search.
 *
 * @param list<int> $nums
 */
function lengthOfLisOptimized(array $nums): int
{
    $tails = []; // tails[i] = smallest tail of LIS of length i+1

    foreach ($nums as $num) {
        $lo = 0;
        $hi = count($tails);
        // Binary search for leftmost position >= num
        while ($lo < $hi) {
            $mid = $lo + intdiv($hi - $lo, 2);
            if ($tails[$mid] < $num) {
                $lo = $mid + 1;
            } else {
                $hi = $mid;
            }
        }
        if ($lo === count($tails)) {
            $tails[] = $num;
        } else {
            $tails[$lo] = $num;
        }
    }

    return count($tails);
}
## Задача 4: Unique Paths

Условие: робот в левом верхнем углу сетки m x n. Может идти только вправо или вниз. Количество путей до правого нижнего угла.

<?php
declare(strict_types=1);

function uniquePaths(int $m, int $n): int
{
    $dp = array_fill(0, $m, array_fill(0, $n, 1));

    for ($i = 1; $i < $m; $i++) {
        for ($j = 1; $j < $n; $j++) {
            $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
        }
    }

    return $dp[$m - 1][$n - 1];
}

// m=3, n=3:
// [[1, 1, 1],
//  [1, 2, 3],
//  [1, 3, 6]]
// Answer: 6
Оптимизация до O(n) памяти: 
<?php
declare(strict_types=1);

function uniquePathsOptimized(int $m, int $n): int
{
    $row = array_fill(0, $n, 1);
    for ($i = 1; $i < $m; $i++) {
        for ($j = 1; $j < $n; $j++) {
            $row[$j] += $row[$j - 1];
        }
    }
    return $row[$n - 1];
}
## Задача 5: Maximum Subarray (Kadane's Algorithm) 
<?php
declare(strict_types=1);

/**
 * @param list<int> $nums
 */
function maxSubarray(array $nums): int
{
    $maxSum = $nums[0];
    $currentSum = $nums[0];

    for ($i = 1; $i < count($nums); $i++) {
        $currentSum = max($nums[$i], $currentSum + $nums[$i]);
        $maxSum = max($maxSum, $currentSum);
    }

    return $maxSum;
}

// nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// current: -2, 1, -2, 4, 3, 5, 6, 1, 5
// max_sum: -2, 1, 1, 4, 4, 5, 6, 6, 6
// Answer: 6 (subarray [4, -1, 2, 1])
## Задача 6: Word Break 
<?php
declare(strict_types=1);

/**
 * @param list<string> $wordDict
 */
function wordBreak(string $s, array $wordDict): bool
{
    $wordSet = array_flip($wordDict);
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, false);
    $dp[0] = true; // Empty string can be segmented

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($dp[$j] && isset($wordSet[substr($s, $j, $i - $j)])) {
                $dp[$i] = true;
                break;
            }
        }
    }

    return $dp[$n];
}

// s = "leetcode", wordDict = ["leet", "code"]
// dp[0]=T
// dp[4]=T (s[0:4]="leet" in dict)
// dp[8]=T (dp[4]=T and s[4:8]="code" in dict)
// Answer: true
## Задача 7: Decode Ways 
<?php
declare(strict_types=1);

function numDecodings(string $s): int
{
    if ($s === '' || $s[0] === '0') {
        return 0;
    }

    $n = strlen($s);
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;
    $dp[1] = 1;

    for ($i = 2; $i <= $n; $i++) {
        // Single digit
        if ($s[$i - 1] !== '0') {
            $dp[$i] += $dp[$i - 1];
        }

        // Two digits
        $twoDigit = (int) substr($s, $i - 2, 2);
        if ($twoDigit >= 10 && $twoDigit <= 26) {
            $dp[$i] += $dp[$i - 2];
        }
    }

    return $dp[$n];
}

// "226" -> "2|2|6", "22|6", "2|26" -> 3 ways
## Шаблоны DP задач
Тип задачи Рекуррентность Пример
Линейная dp[i] = f(dp[i-1], dp[i-2]) Fibonacci, Stairs
На массиве dp[i] = best(dp[j] + ...) for j<i LIS, Word Break
На сетке dp[i][j] = f(dp[i-1][j], dp[i][j-1]) Unique Paths
С выбором dp[i] = max(take, skip) House Robber
На сумму dp[i] = f(dp[i-c]) for c in choices Coin Change

Запомни: Для каждой DP задачи: 1) Определи что dp[i] означает, 2) Найди рекуррентность, 3) Заполни базу, 4) Заполни таблицу. Kadane's Algorithm — самая элегантная DP: один проход, O(1) памяти. LIS с бинарным поиском — O(n log n) оптимизация классической O(n^2).

Итоги

  1. Coin Change: dp[i] = min(dp[i-c]+1) по всем монетам
  2. House Robber: dp[i] = max(dp[i-1], dp[i-2]+nums[i])
  3. LIS: dp[i] = max(dp[j]+1) для j < i, nums[j] < nums[i]
  4. Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]
  5. Kadane: current = max(num, current+num)
  6. Оптимизация памяти: если зависит от 1-2 предыдущих

Проверь себя

Что выведет алгоритм Kadane для массива [-2, 1, -3, 4, -1, 2, 1, -5, 4]?

В задаче House Robber для массива [2, 7, 9, 3, 1], какие дома оптимально ограбить?

В задаче Unique Paths для сетки 3x3, сколько уникальных путей из левого верхнего угла в правый нижний?

Какова временная сложность оптимизированного алгоритма LIS с бинарным поиском?

Для монет [1, 5, 11] и суммы 15, сколько монет нужно минимально?

Связанные темы

Монотонный стек

Связанная тема

Алгоритм Дейкстры

Связанная тема

Задача о рюкзаке

Связанная тема

DP на строках

Связанная тема