Введение в «динамическое программирование» для новичков в алгоритмах

«Эта статья участвовала в мероприятии Haowen Convocation Order, щелкните, чтобы просмотреть:Двойные заявки на внутреннюю и внешнюю стороны, призовой фонд в 20 000 юаней ждет вас, чтобы бросить вызов!"

предисловие

Текущая серия, связанная с «Динамическим программированием» официального аккаунта, включает: «Проблема динамического программирования-Путь», которая была завершена, и «Задача динамического программирования-Рюкзак», которая обновляется.

Это цикл статей о том, что у каждого по умолчанию есть определенное понимание «динамического программирования».

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

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

Следует отметить, что эта статья посвящена только перцептуальному пониманию «динамического программирования» и не углубляется в существенные отношения между динамическим программированием и теорией графов.

Поэтому он больше ориентирован на читателей вводных алгоритмов.

Далее текстовое содержание.

Эволюция

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

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

Однако с точки зрения постепенной оптимизации алгоритма динамическое программирование более развито в следующих направлениях:

Рекурсия грубой силы -> мемоизированный поиск -> динамическое программирование.

Можно даже сказать, что почти все «динамическое программирование» можно преобразовать с помощью «грубой рекурсии», при условии, что проблема является проблемой «без последствий».

От простого перечисления «кейсов» к перечислению «коллекций».

нет последействия

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

Можно просто понять, что после написания рекурсивной функции при определении переменных параметров результат определяется однозначно.

Возможно, вы все еще не понимаете, что такое проблема «отсутствия последействия». Неважно, давайте возьмем более конкретный пример, т.LeetCode 62. Unique Paths: учитывая$m * n$Матрица , из левого верхнего угла в качестве отправной точки, сколько путей есть, чтобы достичь правого нижнего угла (робот может двигаться только вправо или вниз).

Это классическая вводная задача "динамического программирования" и классическая проблема "отсутствия последействия".

Его «отсутствие последействия» выражается в: когда определенное состояние (конкретное$m * n$и некоторая начальная точка, например (1,2)), то количество путей из этой точки в правый нижний угол полностью определено.

Это не имеет никакого отношения к тому, как достигается это «состояние», достигает ли робот (1,2) через точку (0,2) или (1,2) через (1,1).

Это так называемая проблема «отсутствия последействия».

Когда мы пытаемся использовать «динамическое программирование» для решения проблемы, мы должны сначала обратить внимание на то, является ли проблема проблемой «не следствия».

1: грубая рекурсия

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

Мое предложение в настоящее время состоит в том, чтобы сначала написать версию «рекурсивной грубой силы».

или что я только что сказалLeetCode 62. Unique PathsПример:

class Solution {
    public int uniquePaths(int m, int n) {
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

Когда я не знал, как решить это с помощью «динамического программирования», я разработал рекурсивную функцию.$recursive$.

Функция передает в матрицу информацию и текущую позицию робота, и возвращает в этой матрице, сколько путей есть от позиции робота до правого нижнего угла.

С помощью этой рекурсивной функции проблема на самом деле состоит в том, чтобы решить$recursive(m, n, 0, 0)$: Найдите количество путей от (0,0) до правого нижнего угла.

Далее реализуем эту функцию:

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

2. Другие случаи: Робот может идти вправо или вниз, поэтому для определенной позиции количество путей в правый нижний угол равно количеству путей в правый нижний угол из его правого положения + количество путей из его нижнего положение в правом нижнем углу. которыйrecursive(m,n,i+1,j) + recursive(m,n,i,j+1), обе позиции могут быть решены рекурсивной функцией.

По сути, здесь мы решили эту проблему.

Но при таком подходе возникает серьезная проблема «производительности».

2: Поиск в памяти

Если мы отправим приведенный выше код в LeetCode, мы получим результат тайм-аута.

Видно, что решение «насильственной рекурсии» «очень медленное».

Мы знаем, что суть всех рекурсивных функций состоит в том, чтобы «протолкнуть стек» и «вытолкнуть стек».

Поскольку этот процесс медленный, можем ли мы решить проблему тайм-аута, изменив рекурсивную версию решения грубой силы на нерекурсивное решение грубой силы?

Ответ - нет, потому что причина тайм-аута не в затратах на использование "рекурсивных" средств.

Но в процессе расчета мы многократно повторяли расчет.

Давайте попробуем расширить рекурсивный процесс на несколько шагов, чтобы увидеть:

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

По мере развертывания всего нашего рекурсивного процесса количество повторяющихся вычислений растет экспоненциально.

Вот почему решение «рекурсивного грубого перебора» является «медленным».

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

class Solution {
    private int[][] cache;

    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            if (cache[i + 1][j] == -1) {
                cache[i + 1][j] = recursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {
                cache[i][j + 1] = recursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }
}

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

После внесения таких улучшений LeetCode смог представить AC и получить хороший рейтинг.

Если еще немного подумать, то мы обнаружим, что количество посещений для каждой ситуации (каждой точки) не изменилось за весь процесс решения.

Просто улучшено с «решать при каждом предыдущем посещении» до «действительно решать только при первом посещении».

На самом деле, глядя наrecursive()метод можно найти:

когда мы решаем за точку$(i, j)$На самом деле ответ зависит от$(i, j + 1)$и$(i + 1, j)$.

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

Эта ситуация связана с принятым нами подходом «сверху вниз».

Мы не можем интуитивно определить, какие точечные результаты будут посещены, когда и сколько раз.

Таким образом, мы должны использовать массив того же размера, что и матрица, чтобы «кэшировать» все промежуточные результаты.

Другими словами, «запоминаемый поиск» решает проблему повторных вычислений, а не решает проблему неопределенности времени и количества посещений результатов.

2.1: Неоптимальная версия «запоминаемого поиска»

Наконец, давайте поговорим о «поиске в памяти».

В Интернете есть много блогов и материалов, которые пишут код, подобный следующему, при написании решения «запоминаемого поиска»:

class Solution {
    private int[][] cache;

    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            cache[i][j] = recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }
}

Сравните с решением, которое я предоставил выше. Основное отличие в том, чтоif (cache[i][j] == -1)внутри суда.

В моем решении он будет рассчитанcache[i][j], попробуй прочитать из "кеша"cache[i+1][j]иcache[i][j+1], гарантируя, что каждый вызовrecursive()Все обязательные, не повторяющиеся.

Большинство решений в Интернете будут считывать «кеш» только во внешнем слое, когда настоящие вычисленияcache[i][j]Когда он не использует метод сначала проверки, а затем вызова, вызовите его напрямуюrecursive()Вычислительные подзадачи.

Хотя оба значительно сокращают количество вычислений по сравнению с прямой "грубой рекурсией" (recursive()количество посещений), но количество вычислений для последнего, очевидно, намного больше, чем для первого.

Вы можете подумать, что в любом случае это «сверху вниз», между ними не должно быть никакой разницы, верно?

Для этого я предоставляю следующий экспериментальный код, чтобы сравнить их сrecursive()количество звонков:

class Solution {
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.uniquePaths(15, 15);
    }
    
    private int[][] cache;
    private long count; // 统计 递归函数 的调用次数

    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        // int result = recursive(m, n, 0, 0); // count = 80233199
        // int result = cacheRecursive(m, n, 0, 0); // count = 393
        int result = fullCacheRecursive(m, n, 0, 0); // count = 224
        System.out.println(count);
        return result;
    }

    // 完全缓存	
    private int fullCacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            if (cache[i + 1][j] == -1) {
                cache[i + 1][j] = fullCacheRecursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {
                cache[i][j + 1] = fullCacheRecursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }

    // 只有外层缓存
    private int cacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {
            cache[i][j] = cacheRecursive(m, n, i + 1, j) + cacheRecursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }

    // 不使用缓存
    private int recursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

Поскольку наша цель использования массива кеша состоит в том, чтобы уменьшитьrecursive()вызов функции.

Просто убедитесь, что каждый раз, когда вы звонитеrecursive()Прежде чем перейти к массиву кеша для проверки, мы можемrecursive()Количество вызовов функций сведено к минимуму.

С выборкой данных 15 это$O(393n)$и$O(224n)$разница, но это особенно важно для некоторых OJ с особенно серьезными постоянными картами.

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

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

3. От «сверху вниз» к «снизу вверх».

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

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

Как упоминалось ранее, поскольку мы не можем определить время доступа и количество обращений к промежуточным результатам, мы должны «кэшировать» все промежуточные результаты.

Но если мы сможем уточнить время доступа и время доступа к промежуточным результатам, по крайней мере, мы сможем значительно уменьшить объемную сложность алгоритма.

Это включает в себя сдвиг в мышлении решения: от «сверху вниз» к «снизу вверх».

Как реализовать переход от «сверху вниз» к «снизу вверх» следует понять на конкретных примерах.

ЭтоLeetCode 509. Fibonacci Number, знаменитая проблема «последовательности Фибоначчи».

Если вы не знаете, что такое "последовательность Фибоначчи", вы можете проверить соответствующийВикипедия.

Так как формула Фибоначчи:

Естественно использовать рекурсию:

public class Solution {
    private int[] cache;
    public int fib(int n) {
        cache = new int[n + 1];
        return recursive(n);
    }

    private int recursive(int n) {
        if (n <= 1) return n;
        if (n == 2) return 1;
        if (cache[n] == 0) {
            if (cache[n - 1] == 0) {
                cache[n - 1] = recursive(n - 1);
            }
            if (cache[n - 2] == 0) {
                cache[n - 2] = recursive(n - 2);
            } 
            cache[n] = cache[n - 1] + cache[n - 2];
        }
        return cache[n];
    }
}

Но у этого все еще есть проблемы, о которых мы упоминали ранее, и все они вызваны тем фактом, что прямая рекурсия является «сверху вниз».

Пространственно-временная сложность такого решения равна$O(n)$: Вычисляется один раз для каждого значения с использованием длины$n + 1$массив .

Глядя на формулу Фибоначчи, мы видим, что для вычисления определенного$n$, просто нужно знать$n - 1$решение и$n - 2$решение.

в то же время$n = 1$и$n = 2$Решение снова известно (базовый случай).

Таким образом, мы можем получить от$n = 3$Начните и повторяйте шаг за шагом, чтобы получить$n$решение.

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

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        if (n == 2) return 1;
        
        int prev1 = 1, prev2 = 1;
        int cur = prev1 + prev2;
        for (int i = 3; i <= n; i++) {
            cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return cur;
    }
}

Таким образом, мы задаем исходную пространственную сложность как$O(n)$Алгоритм сводится к$O(1)$: просто использовал несколько ограниченных переменных.

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

Это, конечно, не случайно, тем более, что мы написали решение "грубой силы рекурсии".

давайте вернемся сноваLeetCode 62. Unique Pathsсреди:

class Solution {
    public int uniquePaths(int m, int n) {
        // 由于我们的「暴力递归」函数，真正的可变参数就是 i 和 j（ 变化范围分别是 [0,m-1] 和 [0, n-1] ）
        // 所以建议一个二维的 dp 数组进行结果存储（相当于建一个表格）
        int[][] dp = new int[m][n];
        
        // 根据「暴力递归」函数中的 base case
        // 我们可以直接得出 dp 中最后一行和最后一列的值（将表格的最后一行和最后一列填上）
        for (int i = 0; i < n; i++) dp[m - 1][i] = 1
        for (int i = 0; i < m; i++) dp[i][n - 1] = 1;
        
        // 根据「暴力递归」函数中对其他情况的处理逻辑（依赖关系）编写循环
        //（根据表格的最后一行和最后一列的值，得出表格的其他格子的值）
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        
        // 最终我们要的是 dp[0][0]（表格中左上角的位置，也就起点的值）
        return dp[0][0];
        
        // 原「暴力递归」调用
        // return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        // base case
        if (i == m - 1 || j == n - 1) return 1;
        // 其余情况
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

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

Простое «динамическое программирование» на самом деле является «табличным» процессом:

Сначала определить значения некоторых позиций в таблице по базовому варианту, а затем вычислить информацию других сеток по позициям полученных значений.

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

Суть динамического программирования

Суть динамического программирования по-прежнему заключается в перечислении: перебрать все решения и найти оптимальное решение.

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

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

С этой точки зрения «динамическое программирование» и «поиск в памяти» похожи.

Для хранения исторических результатов мы должны использовать структуры данных.В dp мы обычно используем одномерные массивы или двумерные данные для хранения, предполагая dp[].

Тогда у нас есть следующий процесс для решения проблемы dp

1. Определение состояния: определить значение элементов в dp[], то есть необходимо уточнить, что представляет собой dp[i]
2. Переход состояния: определите отношения между элементами dp[], из которых dp решётки получена эта решётка dp[i]. Например, в последовательности Фибоначчи dp[i] = dp[i - 1] + dp[i - 2]
3. Начальное значение: базовый случай, какие сетки в dp[] могут напрямую получить результат. Например, в последовательности Фибоначчи есть dp[0] = 0 и dp[1] = 1.

Убрать «Афтерэффекты»

Мы знаем, что предпосылкой использования «динамического программирования» является «недопустимость» проблемы.

Но иногда «отсутствие последствий» проблемы нелегко отразить.

Нам нужно ввести еще одно измерение, чтобы «устранить».

Например, в классической «задаче запасов» на LeetCode при использовании динамического программирования для решения часто необходимо ввести еще одно измерение для представления состояния, а иногда даже необходимо ввести еще одно измерение для представления количества покупки.

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

Суммировать

На данный момент мы можем просто ответить на разницу между «динамическим программированием» и «поиском в памяти».

Суть «поиска в памяти» заключается в «переборе грубой силы» с функцией «кэширования»:

Он может только решить проблему повторного расчета, но не может определить время доступа и количество обращений к промежуточным результатам.Это по сути решение «сверху вниз»;

«Динамическое программирование» — это решение «снизу вверх»:

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