Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 14.1 Первое знакомство с динамическим программированием

Динамическое программирование (dynamic programming) - это важная алгоритмическая парадигма, которая разбивает задачу на последовательность более мелких подзадач и за счет хранения их решений избегает повторных вычислений, тем самым резко повышая эффективность по времени.

В этом разделе мы начнем с классического примера: сначала представим его грубое решение методом поиска с возвратом, увидим в нем перекрывающиеся подзадачи, а затем постепенно выведем более эффективное решение на основе динамического программирования.

Подъем по лестнице

Дана лестница из \(n\) ступеней. За один шаг можно подняться на \(1\) или на \(2\) ступени. Сколькими способами можно добраться до вершины?

Как показано на рисунке 14-1, для лестницы из \(3\) ступеней существует \(3\) способа добраться до вершины.

Рисунок 14-1 Число способов подняться на 3-ю ступень

Цель этой задачи - вычислить количество способов. Поэтому можно попробовать использовать для ее решения метод поиска с возвратом. Если представить подъем по лестнице как последовательность решений, то мы начинаем от земли и на каждом раунде выбираем прыжок на \(1\) или на \(2\) ступени. Всякий раз, когда достигаем вершины, увеличиваем число способов на \(1\) , а если перескакиваем вершину, обрезаем эту ветвь. Код выглядит так:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
climbing_stairs_backtrack.py

    def backtrack(choices: list[int], state: int, n: int, res: list[int]) -> int:
        """Бэктрекинг"""
        # Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if state == n:
            res[0] += 1
        # Перебор всех вариантов выбора
        for choice in choices:
            # Отсечение: нельзя выходить за n-ю ступень
            if state + choice > n:
                continue
            # Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res)
            # Откат

    def climbing_stairs_backtrack(n: int) -> int:
        """Подъем по лестнице: бэктрекинг"""
        choices = [1, 2]  # Можно подняться на 1 или 2 ступени
        state = 0  # Начать подъем с 0-й ступени
        res = [0]  # Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res)
        return res[0]

climbing_stairs_backtrack.cpp

    /* Бэктрекинг */
    void backtrack(vector<int> &choices, int state, int n, vector<int> &res) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state == n)
            res[0]++;
        // Перебор всех вариантов выбора
        for (auto &choice : choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n)
                continue;
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    int climbingStairsBacktrack(int n) {
        vector<int> choices = {1, 2}; // Можно подняться на 1 или 2 ступени
        int state = 0;                // Начать подъем с 0-й ступени
        vector<int> res = {0};        // Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res);
        return res[0];
    }

climbing_stairs_backtrack.java

    /* Бэктрекинг */
    void backtrack(List<Integer> choices, int state, int n, List<Integer> res) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state == n)
            res.set(0, res.get(0) + 1);
        // Перебор всех вариантов выбора
        for (Integer choice : choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n)
                continue;
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    int climbingStairsBacktrack(int n) {
        List<Integer> choices = Arrays.asList(1, 2); // Можно подняться на 1 или 2 ступени
        int state = 0; // Начать подъем с 0-й ступени
        List<Integer> res = new ArrayList<>();
        res.add(0); // Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res);
        return res.get(0);
    }

climbing_stairs_backtrack.cs

    /* Бэктрекинг */
    void Backtrack(List<int> choices, int state, int n, List<int> res) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state == n)
            res[0]++;
        // Перебор всех вариантов выбора
        foreach (int choice in choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n)
                continue;
            // Попытка: сделать выбор и обновить состояние
            Backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    int ClimbingStairsBacktrack(int n) {
        List<int> choices = [1, 2]; // Можно подняться на 1 или 2 ступени
        int state = 0; // Начать подъем с 0-й ступени
        List<int> res = [0]; // Использовать res[0] для хранения числа решений
        Backtrack(choices, state, n, res);
        return res[0];
    }

climbing_stairs_backtrack.go

    /* Бэктрекинг */
    func backtrack(choices []int, state, n int, res []int) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if state == n {
            res[0] = res[0] + 1
        }
        // Перебор всех вариантов выбора
        for _, choice := range choices {
            // Отсечение: нельзя выходить за n-ю ступень
            if state+choice > n {
                continue
            }
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state+choice, n, res)
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    func climbingStairsBacktrack(n int) int {
        // Можно подняться на 1 или 2 ступени
        choices := []int{1, 2}
        // Начать подъем с 0-й ступени
        state := 0
        res := make([]int, 1)
        // Использовать res[0] для хранения числа решений
        res[0] = 0
        backtrack(choices, state, n, res)
        return res[0]
    }

climbing_stairs_backtrack.swift

    /* Бэктрекинг */
    func backtrack(choices: [Int], state: Int, n: Int, res: inout [Int]) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if state == n {
            res[0] += 1
        }
        // Перебор всех вариантов выбора
        for choice in choices {
            // Отсечение: нельзя выходить за n-ю ступень
            if state + choice > n {
                continue
            }
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices: choices, state: state + choice, n: n, res: &res)
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    func climbingStairsBacktrack(n: Int) -> Int {
        let choices = [1, 2] // Можно подняться на 1 или 2 ступени
        let state = 0 // Начать подъем с 0-й ступени
        var res: [Int] = []
        res.append(0) // Использовать res[0] для хранения числа решений
        backtrack(choices: choices, state: state, n: n, res: &res)
        return res[0]
    }

climbing_stairs_backtrack.js

    /* Бэктрекинг */
    function backtrack(choices, state, n, res) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state === n) res.set(0, res.get(0) + 1);
        // Перебор всех вариантов выбора
        for (const choice of choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n) continue;
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    function climbingStairsBacktrack(n) {
        const choices = [1, 2]; // Можно подняться на 1 или 2 ступени
        const state = 0; // Начать подъем с 0-й ступени
        const res = new Map();
        res.set(0, 0); // Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res);
        return res.get(0);
    }

climbing_stairs_backtrack.ts

    /* Бэктрекинг */
    function backtrack(
        choices: number[],
        state: number,
        n: number,
        res: Map<0, any>
    ): void {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state === n) res.set(0, res.get(0) + 1);
        // Перебор всех вариантов выбора
        for (const choice of choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n) continue;
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    function climbingStairsBacktrack(n: number): number {
        const choices = [1, 2]; // Можно подняться на 1 или 2 ступени
        const state = 0; // Начать подъем с 0-й ступени
        const res = new Map();
        res.set(0, 0); // Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res);
        return res.get(0);
    }

climbing_stairs_backtrack.dart

    /* Бэктрекинг */
    void backtrack(List<int> choices, int state, int n, List<int> res) {
      // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
      if (state == n) {
        res[0]++;
      }
      // Перебор всех вариантов выбора
      for (int choice in choices) {
        // Отсечение: нельзя выходить за n-ю ступень
        if (state + choice > n) continue;
        // Попытка: сделать выбор и обновить состояние
        backtrack(choices, state + choice, n, res);
        // Откат
      }
    }

    /* Подъем по лестнице: бэктрекинг */
    int climbingStairsBacktrack(int n) {
      List<int> choices = [1, 2]; // Можно подняться на 1 или 2 ступени
      int state = 0; // Начать подъем с 0-й ступени
      List<int> res = [];
      res.add(0); // Использовать res[0] для хранения числа решений
      backtrack(choices, state, n, res);
      return res[0];
    }

climbing_stairs_backtrack.rs

    /* Бэктрекинг */
    fn backtrack(choices: &[i32], state: i32, n: i32, res: &mut [i32]) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if state == n {
            res[0] = res[0] + 1;
        }
        // Перебор всех вариантов выбора
        for &choice in choices {
            // Отсечение: нельзя выходить за n-ю ступень
            if state + choice > n {
                continue;
            }
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    fn climbing_stairs_backtrack(n: usize) -> i32 {
        let choices = vec![1, 2]; // Можно подняться на 1 или 2 ступени
        let state = 0; // Начать подъем с 0-й ступени
        let mut res = Vec::new();
        res.push(0); // Использовать res[0] для хранения числа решений
        backtrack(&choices, state, n as i32, &mut res);
        res[0]
    }

climbing_stairs_backtrack.c

    /* Бэктрекинг */
    void backtrack(int *choices, int state, int n, int *res, int len) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state == n)
            res[0]++;
        // Перебор всех вариантов выбора
        for (int i = 0; i < len; i++) {
            int choice = choices[i];
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n)
                continue;
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res, len);
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    int climbingStairsBacktrack(int n) {
        int choices[2] = {1, 2}; // Можно подняться на 1 или 2 ступени
        int state = 0;           // Начать подъем с 0-й ступени
        int *res = (int *)malloc(sizeof(int));
        *res = 0; // Использовать res[0] для хранения числа решений
        int len = sizeof(choices) / sizeof(int);
        backtrack(choices, state, n, res, len);
        int result = *res;
        free(res);
        return result;
    }

climbing_stairs_backtrack.kt

    /* Бэктрекинг */
    fun backtrack(
        choices: MutableList<Int>,
        state: Int,
        n: Int,
        res: MutableList<Int>
    ) {
        // Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
        if (state == n)
            res[0] = res[0] + 1
        // Перебор всех вариантов выбора
        for (choice in choices) {
            // Отсечение: нельзя выходить за n-ю ступень
            if (state + choice > n) continue
            // Попытка: сделать выбор и обновить состояние
            backtrack(choices, state + choice, n, res)
            // Откат
        }
    }

    /* Подъем по лестнице: бэктрекинг */
    fun climbingStairsBacktrack(n: Int): Int {
        val choices = mutableListOf(1, 2) // Можно подняться на 1 или 2 ступени
        val state = 0 // Начать подъем с 0-й ступени
        val res = mutableListOf<Int>()
        res.add(0) // Использовать res[0] для хранения числа решений
        backtrack(choices, state, n, res)
        return res[0]
    }

climbing_stairs_backtrack.rb

    ### Бэктрекинг ###
    def backtrack(choices, state, n, res)
      # Когда подъем достигает n-й ступени, число вариантов увеличивается на 1
      res[0] += 1 if state == n
      # Перебор всех вариантов выбора
      for choice in choices
        # Отсечение: нельзя выходить за n-ю ступень
        next if state + choice > n

        # Попытка: сделать выбор и обновить состояние
        backtrack(choices, state + choice, n, res)
      end
      # Откат
    end

    ### Подъем по лестнице: бэктрекинг ###
    def climbing_stairs_backtrack(n)
      choices = [1, 2] # Можно подняться на 1 или 2 ступени
      state = 0 # Начать подъем с 0-й ступени
      res = [0] # Использовать res[0] для хранения числа решений
      backtrack(choices, state, n, res)
      res.first
    end

Визуализация кода

Во весь экран >

## 14.1.1 Метод 1: полный перебор

Алгоритм поиска с возвратом обычно не раскладывает задачу явно на подзадачи. Вместо этого он рассматривает решение как последовательность решений, используя попытки и обрезку для поиска всех возможных ответов.

Попробуем посмотреть на задачу именно как на разложение подзадач. Пусть число способов добраться до ступени \(i\) равно \(dp[i]\). Тогда \(dp[i]\) - это исходная задача, а ее подзадачи включают:

\[ dp[i-1], dp[i-2], \dots, dp[2], dp[1] \]

Поскольку за один раунд можно подняться только на \(1\) или на \(2\) ступени, стоя на ступени \(i\) , в предыдущий раунд мы могли находиться только на ступени \(i - 1\) или на ступени \(i - 2\) . Иначе говоря, на ступень \(i\) можно попасть только со ступени \(i -1\) или со ступени \(i - 2\) .

Отсюда получается важный вывод: число способов добраться до ступени \(i - 1\) плюс число способов добраться до ступени \(i - 2\) равно числу способов добраться до ступени \(i\). Формула имеет вид:

\[ dp[i] = dp[i-1] + dp[i-2] \]

Это означает, что в задаче о подъеме по лестнице между подзадачами существует рекуррентная зависимость, и решение исходной задачи может быть построено на основе решений подзадач. Эта связь показана на рисунке 14-2.

Рисунок 14-2 Рекуррентная связь числа способов

По рекуррентной формуле можно получить решение полного перебора. Начиная с \(dp[n]\) , мы рекурсивно разлагаем большую задачу в сумму двух меньших задач , пока не дойдем до наименьших подзадач \(dp[1]\) и \(dp[2]\) . Их решения уже известны: \(dp[1] = 1\) и \(dp[2] = 2\) , что означает \(1\) и \(2\) способа подняться соответственно на \(1\)-ю и \(2\)-ю ступени.

Посмотрите на следующий код: как и стандартный поиск с возвратом, он относится к поиску в глубину, но выглядит более компактно:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
climbing_stairs_dfs.py

    def dfs(i: int) -> int:
        """Поиск"""
        # dp[1] и dp[2] уже известны, вернуть их
        if i == 1 or i == 2:
            return i
        # dp[i] = dp[i-1] + dp[i-2]
        count = dfs(i - 1) + dfs(i - 2)
        return count

    def climbing_stairs_dfs(n: int) -> int:
        """Подъем по лестнице: поиск"""
        return dfs(n)

climbing_stairs_dfs.cpp

    /* Поиск */
    int dfs(int i) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1) + dfs(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    int climbingStairsDFS(int n) {
        return dfs(n);
    }

climbing_stairs_dfs.java

    /* Поиск */
    int dfs(int i) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1) + dfs(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    int climbingStairsDFS(int n) {
        return dfs(n);
    }

climbing_stairs_dfs.cs

    /* Поиск */
    int DFS(int i) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // dp[i] = dp[i-1] + dp[i-2]
        int count = DFS(i - 1) + DFS(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    int ClimbingStairsDFS(int n) {
        return DFS(n);
    }

climbing_stairs_dfs.go

    /* Поиск */
    func dfs(i int) int {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i
        }
        // dp[i] = dp[i-1] + dp[i-2]
        count := dfs(i-1) + dfs(i-2)
        return count
    }

    /* Подъем по лестнице: поиск */
    func climbingStairsDFS(n int) int {
        return dfs(n)
    }

climbing_stairs_dfs.swift

    /* Поиск */
    func dfs(i: Int) -> Int {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i
        }
        // dp[i] = dp[i-1] + dp[i-2]
        let count = dfs(i: i - 1) + dfs(i: i - 2)
        return count
    }

    /* Подъем по лестнице: поиск */
    func climbingStairsDFS(n: Int) -> Int {
        dfs(i: n)
    }

climbing_stairs_dfs.js

    /* Поиск */
    function dfs(i) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i === 1 || i === 2) return i;
        // dp[i] = dp[i-1] + dp[i-2]
        const count = dfs(i - 1) + dfs(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    function climbingStairsDFS(n) {
        return dfs(n);
    }

climbing_stairs_dfs.ts

    /* Поиск */
    function dfs(i: number): number {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i === 1 || i === 2) return i;
        // dp[i] = dp[i-1] + dp[i-2]
        const count = dfs(i - 1) + dfs(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    function climbingStairsDFS(n: number): number {
        return dfs(n);
    }

climbing_stairs_dfs.dart

    /* Поиск */
    int dfs(int i) {
      // dp[1] и dp[2] уже известны, вернуть их
      if (i == 1 || i == 2) return i;
      // dp[i] = dp[i-1] + dp[i-2]
      int count = dfs(i - 1) + dfs(i - 2);
      return count;
    }

    /* Подъем по лестнице: поиск */
    int climbingStairsDFS(int n) {
      return dfs(n);
    }

climbing_stairs_dfs.rs

    /* Поиск */
    fn dfs(i: usize) -> i32 {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i as i32;
        }
        // dp[i] = dp[i-1] + dp[i-2]
        let count = dfs(i - 1) + dfs(i - 2);
        count
    }

    /* Подъем по лестнице: поиск */
    fn climbing_stairs_dfs(n: usize) -> i32 {
        dfs(n)
    }

climbing_stairs_dfs.c

    /* Поиск */
    int dfs(int i) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1) + dfs(i - 2);
        return count;
    }

    /* Подъем по лестнице: поиск */
    int climbingStairsDFS(int n) {
        return dfs(n);
    }

climbing_stairs_dfs.kt

    /* Поиск */
    fun dfs(i: Int): Int {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2) return i
        // dp[i] = dp[i-1] + dp[i-2]
        val count = dfs(i - 1) + dfs(i - 2)
        return count
    }

    /* Подъем по лестнице: поиск */
    fun climbingStairsDFS(n: Int): Int {
        return dfs(n)
    }

climbing_stairs_dfs.rb

    ### Поиск ###
    def dfs(i)
      # dp[1] и dp[2] уже известны, вернуть их
      return i if i == 1 || i == 2
      # dp[i] = dp[i-1] + dp[i-2]
      dfs(i - 1) + dfs(i - 2)
    end

    ### Подъем по лестнице: поиск ###
    def climbing_stairs_dfs(n)
      dfs(n)
    end

Визуализация кода

Во весь экран >

На рисунке 14-3 показано дерево рекурсии, возникающее при полном переборе. Для задачи \(dp[n]\) глубина дерева рекурсии равна \(n\) , а временная сложность равна \(O(2^n)\) . Экспоненциальный рост взрывообразен: если подать на вход достаточно большое значение \(n\) , ожидание станет очень долгим.

Рисунок 14-3 Дерево рекурсии для подъема по лестнице

Как видно на рисунке 14-3, экспоненциальная временная сложность порождается «перекрывающимися подзадачами». Например, \(dp[9]\) раскладывается в \(dp[8]\) и \(dp[7]\) , а \(dp[8]\) - в \(dp[7]\) и \(dp[6]\). Обе ветви содержат подзадачу \(dp[7]\) .

Продолжая это рассуждение, мы видим, что подзадачи порождают все более мелкие перекрывающиеся подзадачи без конца. Подавляющая часть вычислительных ресурсов уходит именно на них.

## 14.1.2 Метод 2: поиск с мемоизацией

Чтобы ускорить алгоритм, мы хотим, чтобы каждая перекрывающаяся подзадача вычислялась только один раз. Для этого объявим массив `mem` для хранения решения каждой подзадачи и будем обрезать повторные вычисления в процессе поиска.

1. Когда \(dp[i]\) вычисляется впервые, мы сохраняем его в `mem[i]` для последующего использования.
2. Когда значение \(dp[i]\) требуется снова, мы просто берем его напрямую из `mem[i]` и тем самым избегаем повторного вычисления подзадачи.

Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
climbing_stairs_dfs_mem.py

    def dfs(i: int, mem: list[int]) -> int:
        """Поиск с мемоизацией"""
        # dp[1] и dp[2] уже известны, вернуть их
        if i == 1 or i == 2:
            return i
        # Если запись dp[i] существует, сразу вернуть ее
        if mem[i] != -1:
            return mem[i]
        # dp[i] = dp[i-1] + dp[i-2]
        count = dfs(i - 1, mem) + dfs(i - 2, mem)
        # Сохранить dp[i]
        mem[i] = count
        return count

    def climbing_stairs_dfs_mem(n: int) -> int:
        """Подъем по лестнице: поиск с мемоизацией"""
        # mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        mem = [-1] * (n + 1)
        return dfs(n, mem)

climbing_stairs_dfs_mem.cpp

    /* Поиск с мемоизацией */
    int dfs(int i, vector<int> &mem) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1)
            return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    int climbingStairsDFSMem(int n) {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        vector<int> mem(n + 1, -1);
        return dfs(n, mem);
    }

climbing_stairs_dfs_mem.java

    /* Поиск с мемоизацией */
    int dfs(int i, int[] mem) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1)
            return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    int climbingStairsDFSMem(int n) {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        int[] mem = new int[n + 1];
        Arrays.fill(mem, -1);
        return dfs(n, mem);
    }

climbing_stairs_dfs_mem.cs

    /* Поиск с мемоизацией */
    int DFS(int i, int[] mem) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1)
            return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        int count = DFS(i - 1, mem) + DFS(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    int ClimbingStairsDFSMem(int n) {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        int[] mem = new int[n + 1];
        Array.Fill(mem, -1);
        return DFS(n, mem);
    }

climbing_stairs_dfs_mem.go

    /* Поиск с мемоизацией */
    func dfsMem(i int, mem []int) int {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i
        }
        // Если запись dp[i] существует, сразу вернуть ее
        if mem[i] != -1 {
            return mem[i]
        }
        // dp[i] = dp[i-1] + dp[i-2]
        count := dfsMem(i-1, mem) + dfsMem(i-2, mem)
        // Сохранить dp[i]
        mem[i] = count
        return count
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    func climbingStairsDFSMem(n int) int {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        mem := make([]int, n+1)
        for i := range mem {
            mem[i] = -1
        }
        return dfsMem(n, mem)
    }

climbing_stairs_dfs_mem.swift

    /* Поиск с мемоизацией */
    func dfs(i: Int, mem: inout [Int]) -> Int {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i
        }
        // Если запись dp[i] существует, сразу вернуть ее
        if mem[i] != -1 {
            return mem[i]
        }
        // dp[i] = dp[i-1] + dp[i-2]
        let count = dfs(i: i - 1, mem: &mem) + dfs(i: i - 2, mem: &mem)
        // Сохранить dp[i]
        mem[i] = count
        return count
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    func climbingStairsDFSMem(n: Int) -> Int {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        var mem = Array(repeating: -1, count: n + 1)
        return dfs(i: n, mem: &mem)
    }

climbing_stairs_dfs_mem.js

    /* Поиск с мемоизацией */
    function dfs(i, mem) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i === 1 || i === 2) return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1) return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        const count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    function climbingStairsDFSMem(n) {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        const mem = new Array(n + 1).fill(-1);
        return dfs(n, mem);
    }

climbing_stairs_dfs_mem.ts

    /* Поиск с мемоизацией */
    function dfs(i: number, mem: number[]): number {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i === 1 || i === 2) return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1) return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        const count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    function climbingStairsDFSMem(n: number): number {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        const mem = new Array(n + 1).fill(-1);
        return dfs(n, mem);
    }

climbing_stairs_dfs_mem.dart

    /* Поиск с мемоизацией */
    int dfs(int i, List<int> mem) {
      // dp[1] и dp[2] уже известны, вернуть их
      if (i == 1 || i == 2) return i;
      // Если запись dp[i] существует, сразу вернуть ее
      if (mem[i] != -1) return mem[i];
      // dp[i] = dp[i-1] + dp[i-2]
      int count = dfs(i - 1, mem) + dfs(i - 2, mem);
      // Сохранить dp[i]
      mem[i] = count;
      return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    int climbingStairsDFSMem(int n) {
      // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
      List<int> mem = List.filled(n + 1, -1);
      return dfs(n, mem);
    }

climbing_stairs_dfs_mem.rs

    /* Поиск с мемоизацией */
    fn dfs(i: usize, mem: &mut [i32]) -> i32 {
        // dp[1] и dp[2] уже известны, вернуть их
        if i == 1 || i == 2 {
            return i as i32;
        }
        // Если запись dp[i] существует, сразу вернуть ее
        if mem[i] != -1 {
            return mem[i];
        }
        // dp[i] = dp[i-1] + dp[i-2]
        let count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        count
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    fn climbing_stairs_dfs_mem(n: usize) -> i32 {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        let mut mem = vec![-1; n + 1];
        dfs(n, &mut mem)
    }

climbing_stairs_dfs_mem.c

    /* Поиск с мемоизацией */
    int dfs(int i, int *mem) {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2)
            return i;
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1)
            return mem[i];
        // dp[i] = dp[i-1] + dp[i-2]
        int count = dfs(i - 1, mem) + dfs(i - 2, mem);
        // Сохранить dp[i]
        mem[i] = count;
        return count;
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    int climbingStairsDFSMem(int n) {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        int *mem = (int *)malloc((n + 1) * sizeof(int));
        for (int i = 0; i <= n; i++) {
            mem[i] = -1;
        }
        int result = dfs(n, mem);
        free(mem);
        return result;
    }

climbing_stairs_dfs_mem.kt

    /* Поиск с мемоизацией */
    fun dfs(i: Int, mem: IntArray): Int {
        // dp[1] и dp[2] уже известны, вернуть их
        if (i == 1 || i == 2) return i
        // Если запись dp[i] существует, сразу вернуть ее
        if (mem[i] != -1) return mem[i]
        // dp[i] = dp[i-1] + dp[i-2]
        val count = dfs(i - 1, mem) + dfs(i - 2, mem)
        // Сохранить dp[i]
        mem[i] = count
        return count
    }

    /* Подъем по лестнице: поиск с мемоизацией */
    fun climbingStairsDFSMem(n: Int): Int {
        // mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
        val mem = IntArray(n + 1)
        mem.fill(-1)
        return dfs(n, mem)
    }

climbing_stairs_dfs_mem.rb

    ### Поиск с мемоизацией ###
    def dfs(i, mem)
      # dp[1] и dp[2] уже известны, вернуть их
      return i if i == 1 || i == 2
      # Если запись dp[i] существует, сразу вернуть ее
      return mem[i] if mem[i] != -1

      # dp[i] = dp[i-1] + dp[i-2]
      count = dfs(i - 1, mem) + dfs(i - 2, mem)
      # Сохранить dp[i]
      mem[i] = count
    end

    ### Подъем по лестнице: поиск с мемоизацией ###
    def climbing_stairs_dfs_mem(n)
      # mem[i] хранит число способов подняться на i-ю ступень, -1 означает отсутствие записи
      mem = Array.new(n + 1, -1)
      dfs(n, mem)
    end

Визуализация кода

Во весь экран >

Как показано на рисунке 14-4, после введения мемоизации каждая перекрывающаяся подзадача вычисляется только один раз, и временная сложность оптимизируется до \(O(n)\) . Это огромный скачок в эффективности.

Рисунок 14-4 Дерево рекурсии для поиска с мемоизацией

## 14.1.3 Метод 3: динамическое программирование

Поиск с мемоизацией - это метод «сверху вниз» : мы начинаем с исходной задачи (корня), рекурсивно раскладываем более крупные подзадачи на меньшие, пока не достигнем наименьших подзадач с уже известным ответом (листьев). Затем в процессе возврата постепенно собираем решения подзадач и тем самым получаем решение исходной задачи.

Напротив, динамическое программирование - это метод «снизу вверх» : начиная с решений наименьших подзадач, мы итеративно строим решения для более крупных подзадач, пока не получим ответ на исходную задачу.

Поскольку в динамическом программировании нет этапа возврата, для его реализации достаточно обычных циклов, без рекурсии. В приведенном ниже коде мы инициализируем массив `dp` для хранения решений подзадач. Он выполняет ту же роль, что и массив `mem` в мемоизированном поиске:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
climbing_stairs_dp.py

    def climbing_stairs_dp(n: int) -> int:
        """Подъем по лестнице: динамическое программирование"""
        if n == 1 or n == 2:
            return n
        # Инициализация таблицы dp для хранения решений подзадач
        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]

climbing_stairs_dp.cpp

    /* Подъем по лестнице: динамическое программирование */
    int climbingStairsDP(int n) {
        if (n == 1 || n == 2)
            return n;
        // Инициализация таблицы dp для хранения решений подзадач
        vector<int> dp(n + 1);
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

climbing_stairs_dp.java

    /* Подъем по лестнице: динамическое программирование */
    int climbingStairsDP(int n) {
        if (n == 1 || n == 2)
            return n;
        // Инициализация таблицы dp для хранения решений подзадач
        int[] dp = new int[n + 1];
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

climbing_stairs_dp.cs

    /* Подъем по лестнице: динамическое программирование */
    int ClimbingStairsDP(int n) {
        if (n == 1 || n == 2)
            return n;
        // Инициализация таблицы dp для хранения решений подзадач
        int[] dp = new int[n + 1];
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

climbing_stairs_dp.go

    /* Подъем по лестнице: динамическое программирование */
    func climbingStairsDP(n int) int {
        if n == 1 || n == 2 {
            return n
        }
        // Инициализация таблицы dp для хранения решений подзадач
        dp := make([]int, n+1)
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1
        dp[2] = 2
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for i := 3; i <= n; i++ {
            dp[i] = dp[i-1] + dp[i-2]
        }
        return dp[n]
    }

climbing_stairs_dp.swift

    /* Подъем по лестнице: динамическое программирование */
    func climbingStairsDP(n: Int) -> Int {
        if n == 1 || n == 2 {
            return n
        }
        // Инициализация таблицы dp для хранения решений подзадач
        var dp = Array(repeating: 0, count: n + 1)
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1
        dp[2] = 2
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for i in 3 ... n {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }

climbing_stairs_dp.js

    /* Подъем по лестнице: динамическое программирование */
    function climbingStairsDP(n) {
        if (n === 1 || n === 2) return n;
        // Инициализация таблицы dp для хранения решений подзадач
        const dp = new Array(n + 1).fill(-1);
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (let i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

climbing_stairs_dp.ts

    /* Подъем по лестнице: динамическое программирование */
    function climbingStairsDP(n: number): number {
        if (n === 1 || n === 2) return n;
        // Инициализация таблицы dp для хранения решений подзадач
        const dp = new Array(n + 1).fill(-1);
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (let i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

climbing_stairs_dp.dart

    /* Подъем по лестнице: динамическое программирование */
    int climbingStairsDP(int n) {
      if (n == 1 || n == 2) return n;
      // Инициализация таблицы dp для хранения решений подзадач
      List<int> dp = List.filled(n + 1, 0);
      // Начальное состояние: заранее задать решения наименьших подзадач
      dp[1] = 1;
      dp[2] = 2;
      // Переход состояний: постепенное решение больших подзадач через меньшие
      for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
    }

climbing_stairs_dp.rs

    /* Подъем по лестнице: динамическое программирование */
    fn climbing_stairs_dp(n: usize) -> i32 {
        // dp[1] и dp[2] уже известны, вернуть их
        if n == 1 || n == 2 {
            return n as i32;
        }
        // Инициализация таблицы dp для хранения решений подзадач
        let mut dp = vec![-1; n + 1];
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for i in 3..=n {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        dp[n]
    }

climbing_stairs_dp.c

    /* Подъем по лестнице: динамическое программирование */
    int climbingStairsDP(int n) {
        if (n == 1 || n == 2)
            return n;
        // Инициализация таблицы dp для хранения решений подзадач
        int *dp = (int *)malloc((n + 1) * sizeof(int));
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1;
        dp[2] = 2;
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int result = dp[n];
        free(dp);
        return result;
    }

climbing_stairs_dp.kt

    /* Подъем по лестнице: динамическое программирование */
    fun climbingStairsDP(n: Int): Int {
        if (n == 1 || n == 2) return n
        // Инициализация таблицы dp для хранения решений подзадач
        val dp = IntArray(n + 1)
        // Начальное состояние: заранее задать решения наименьших подзадач
        dp[1] = 1
        dp[2] = 2
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for (i in 3..n) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }

climbing_stairs_dp.rb

    ### Подъем по лестнице: динамическое программирование ###
    def climbing_stairs_dp(n)
      return n  if n == 1 || n == 2

      # Инициализация таблицы dp для хранения решений подзадач
      dp = Array.new(n + 1, 0)
      # Начальное состояние: заранее задать решения наименьших подзадач
      dp[1], dp[2] = 1, 2
      # Переход состояний: постепенное решение больших подзадач через меньшие
      (3...(n + 1)).each { |i| dp[i] = dp[i - 1] + dp[i - 2] }

      dp[n]
    end

Визуализация кода

Во весь экран >

На рисунке 14-5 смоделирован процесс выполнения этого кода.

Рисунок 14-5 Процесс динамического программирования для подъема по лестнице

Как и в поиске с возвратом, в динамическом программировании используется понятие «состояние» для обозначения некоторого этапа решения задачи. Каждое состояние соответствует одной подзадаче и ее локально оптимальному решению. Например, в задаче о лестнице состояние определяется текущим номером ступени \(i\) .

На основе сказанного можно подвести несколько часто используемых терминов динамического программирования.

- Массив `dp` называют таблицей dp, а \(dp[i]\) обозначает решение подзадачи, соответствующей состоянию \(i\) .
- Состояния, соответствующие наименьшим подзадачам (первая и вторая ступени), называют начальными состояниями.
- Рекуррентную формулу \(dp[i] = dp[i-1] + dp[i-2]\) называют уравнением перехода состояния.

## 14.1.4 Оптимизация пространства

Внимательный читатель мог заметить, что поскольку \(dp[i]\) зависит только от \(dp[i-1]\) и \(dp[i-2]\) , нам не нужен весь массив `dp` для хранения ответов всех подзадач. Достаточно двух переменных, которые будут «перекатываться» вперед. Код имеет вид:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
climbing_stairs_dp.py

    def climbing_stairs_dp_comp(n: int) -> int:
        """Подъем по лестнице: динамическое программирование с оптимизацией памяти"""
        if n == 1 or n == 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

climbing_stairs_dp.cpp

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    int climbingStairsDPComp(int n) {
        if (n == 1 || n == 2)
            return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.java

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    int climbingStairsDPComp(int n) {
        if (n == 1 || n == 2)
            return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.cs

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    int ClimbingStairsDPComp(int n) {
        if (n == 1 || n == 2)
            return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.go

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    func climbingStairsDPComp(n int) int {
        if n == 1 || n == 2 {
            return n
        }
        a, b := 1, 2
        // Переход состояний: постепенное решение больших подзадач через меньшие
        for i := 3; i <= n; i++ {
            a, b = b, a+b
        }
        return b
    }

climbing_stairs_dp.swift

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    func climbingStairsDPComp(n: Int) -> Int {
        if n == 1 || n == 2 {
            return n
        }
        var a = 1
        var b = 2
        for _ in 3 ... n {
            (a, b) = (b, a + b)
        }
        return b
    }

climbing_stairs_dp.js

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    function climbingStairsDPComp(n) {
        if (n === 1 || n === 2) return n;
        let a = 1,
            b = 2;
        for (let i = 3; i <= n; i++) {
            const tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.ts

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    function climbingStairsDPComp(n: number): number {
        if (n === 1 || n === 2) return n;
        let a = 1,
            b = 2;
        for (let i = 3; i <= n; i++) {
            const tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.dart

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    int climbingStairsDPComp(int n) {
      if (n == 1 || n == 2) return n;
      int a = 1, b = 2;
      for (int i = 3; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
      }
      return b;
    }

climbing_stairs_dp.rs

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    fn climbing_stairs_dp_comp(n: usize) -> i32 {
        if n == 1 || n == 2 {
            return n as i32;
        }
        let (mut a, mut b) = (1, 2);
        for _ in 3..=n {
            let tmp = b;
            b = a + b;
            a = tmp;
        }
        b
    }

climbing_stairs_dp.c

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    int climbingStairsDPComp(int n) {
        if (n == 1 || n == 2)
            return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = a + b;
            a = tmp;
        }
        return b;
    }

climbing_stairs_dp.kt

    /* Подъем по лестнице: динамическое программирование с оптимизацией памяти */
    fun climbingStairsDPComp(n: Int): Int {
        if (n == 1 || n == 2) return n
        var a = 1
        var b = 2
        for (i in 3..n) {
            val temp = b
            b += a
            a = temp
        }
        return b
    }

climbing_stairs_dp.rb

    ### Подъем по лестнице: динамическое программирование с оптимизацией памяти ###
    def climbing_stairs_dp_comp(n)
      return n if n == 1 || n == 2

      a, b = 1, 2
      (3...(n + 1)).each { a, b = b, a + b }

      b
    end

Визуализация кода

Во весь экран >

Из кода видно, что после отказа от массива `dp` пространственная сложность уменьшается с \(O(n)\) до \(O(1)\) .

Во многих задачах динамического программирования текущее состояние зависит лишь от ограниченного числа предыдущих состояний. Тогда можно сохранять только действительно нужные состояния и за счет «уменьшения размерности» экономить память. Этот прием оптимизации памяти называют «скользящими переменными» или «скользящим массивом».

##### Оставляйте свои идеи, вопросы и предложения в комментариях