Skip to content

Dynamic&Greedy_Programming.MD

Latest commit

 

History

History
104 lines (82 loc) · 6.82 KB

Dynamic&Greedy_Programming.MD

File metadata and controls

104 lines (82 loc) · 6.82 KB

Динамическое и жадное программирование

Содержание:

Dynamic Programming

Dynamic Programming - это способ решения проблем путем сведения проблемы к меньшим подпроблемам.

Вот какими характеристиками должна обладать задача, чтобы решить ее этим способом:

  1. Имеет оптимальную подструктуру (optimal substructure): задача может быть разбита на меньшие подпроблемы, которые в свою очередь также разбиваются на еще меньшие, пока решение не становится тривиальным
  2. Имеет overlapping subproblems: решение для текущего случая переиспользует решение для предыдущего случая

Greedy Programming

Greedy Programming - это способ решения проблем путем попытки на каждом шаге алгоритма получить лучшее решение здесь и сейчас.

Greedy Programming Vs Dynamic Programming

Greedy Programming способ решения алгоритмов похож на DP, но все-таки отличается.

Вот в чем они похожи:

  1. Для каждой проблемы мы пытаемся получить лучшее решение

Вот их отличия:

  1. В greedy на каждом шаге мы пытаемся получить лучшее решение здесь и сейчас. Мы не смотрим есть ли варианты получше, если отойти на пару шагов назад. Таким образом, когда в greedy мы выбираем большее значение на каждом шаге, мы надеемся достигнуть большего конечного решения. Этот концепт называется greedy choice property. Greedy алгоритм доверяет вычисленному на предыдущем шаге решению. но это может не всегда сработать, т.к. то что мы имеем лучшую ситуацию здесь и сейчас, не значит что глобально мы придем к лучшему результату
  2. В DP обязательно есть рекуррентная формула, которая переиспользует решения меньших подпроблем. Greedy алгоритм же не переиспользует решения меньших проблем - он лишь имеет своеобразный accumulator, который постепенно увеличивается с каждым шагом

Примеры задач

[Dynamic Programming] Longest Common Subsequence

Проблема Longest Common Subsequence (LCS) - это классический пример DP.

Вот решение проблемы на Java с пояснениями:

public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // идея:
        // dp[i][j] - это макс. длина общей подпоследовательности для элемента i первой строки и элемента j второй строки
        //
        // 1. если text1[i] != text2[j], то мы берем прошлую максимальную длину из:
        // подстрок text1[0;i], text2[0;j - 1]
        // ИЛИ
        // подстрок text1[0;i - 1], text2[0;j]
        // , что есть max(dp[i][j - 1], dp[i - 1][j])
        // это так, потому что нам ничего не остается кроме как взять какой-то предыдущий максимум, потому что для каждой позиции
        // мы хотим сохранять максимальную длину
        // очевидно, этот предыдущий максимум - это максимум из вышеуказанных подстрок
        //
        // 2. если text1[i] == text2[j], то мы берем прошлую максимальную длину из подстрок text1[0;i - 1], text2[0;j - 1]
        // и добавляем 1
        // , что есть dp[i - 1][j - 1] + 1
        // это так, потому что именно в dp[i - 1][j - 1] лежит максимальная длина для подстрок, оканчивающихся перед
        // текущей позицией
        // то есть, находя совпадение, мы каждый раз улучшаем результат для подстрок text1[0;i - 1] и text2[0;j - 1]
        // ---
        // эта задача - это классический dp:
        // 1. Имеет оптимальную подструктуру (optimal substructure): задача может быть разбита на меньшие подпроблемы, которые
        // в свою очередь также разбиваются на еще меньшие, пока решение не становится тривиальным
        //
        // в LCS - это начало вычислений с подстроки text1 размером 1, каждый раз добавляя к решению новый элемент подстроки
        //
        // 2. Имеет overlapping subproblems: решение для текущего случая переиспользует решение для предыдущего случая
        //
        // в LCS - это переиспользование решения для меньших подстрок, чем текущая строка
        int n = text1.length(), m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }
}