Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

👨‍💻 Алгоритм:

1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге.

2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.

3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.

😎 Решение:

function numWays($steps, $arrLen) {
    $mod = 1000000007;
    $max_pos = min($arrLen - 1, $steps);
    $dp = array_fill(0, $max_pos + 1, 0);
    $dp[0] = 1;
    for ($step = 0; $step < $steps; $step++) {
        $new_dp = array_fill(0, $max_pos + 1, 0);
        for ($i = 0; $i <= $max_pos; $i++) {
            $new_dp[$i] = $dp[$i] % $mod;
            if ($i > 0) $new_dp[$i] = ($new_dp[$i] + $dp[$i - 1]) % $mod;
            if ($i < $max_pos) $new_dp[$i] = ($new_dp[$i] + $dp[$i + 1]) % $mod;
        }
        $dp = $new_dp;
    }
    return $dp[0];
}

Ставь 👍 и забирай 📚 Базу знаний