Динамическое программирование — это алгоритм, который решает заданную сложную проблему, разбивая ее на подзадачи и сохраняя результаты подзадач, чтобы избежать повторного вычисления одного и того же результата.
Ниже приведены два основных свойства проблемы, которые указывают на то, что данная проблема может быть решена с помощью динамического программирования.
- повторяющиеся подзадачи
- Лучшая подструктура
Перекрывающиеся подзадачи:
Подобно разделяй и властвуй, динамическое программирование сочетает в себе решения подзадач. Динамическое программирование в основном используется для решения сложных задач, требующих многократного вычисления одних и тех же подзадач. В динамическом программировании вычислительные решения подзадач хранятся в таблице, поэтому их не нужно вычислять заново. Таким образом, динамическое программирование бесполезно, когда нет общих (перекрывающихся) подзадач. Например, бинарный поиск не имеет общих подзадач. Если мы возьмем в качестве примера рекурсивную программу чисел Фибоначчи, то получим множество подзадач, которые решаются снова и снова.
/* simple recursive program for Fibonacci numbers */
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
Recursion tree for execution of fib(5)
Мы видим, что функция fib(3) вызывается 2 раза. Если мы уже сохранили значение fib(3), вместо того, чтобы вычислять его снова, мы можем повторно использовать старое сохраненное значение. Есть два разных способа хранения значений, чтобы их можно было использовать повторно:
- Мемоизация (сверху вниз)
- Табулирование (снизу вверх)
Мемоизация (сверху вниз)
Воменая программа для проблемы аналогична рекурсивной версии, просто глядя на таблицу поиска перед вычислением решения. Мы инициализируем массив поиска со всеми начальными значениями Nil. Всякий раз, когда нам нужно решить подпроблему, мы сначала посмотрим на таблицу поиска. Если предварительное значение существует, то мы возвращаем это значение, в противном случае мы вычисляем его и помещаем результат в таблицу поиска, чтобы ее можно было повторно использовать позже.
Ниже представлена версия Memoization n-го числа Фибоначчи.
public class Fibonacci {
final int MAX = 100;
final int NIL = -1;
int lookup[] = new int[MAX];
void _initialize() {
for (int i = 0; i < MAX; i++) {
lookup[i] = NIL;
}
}
int fib(int n) {
if (lookup[n] == NIL) {
if (n <= 1)
lookup[n] = n;
else
lookup[n] = fib(n - 1) + fib(n - 2);
}
return lookup[n];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Fibonacci f = new Fibonacci();
int n = 10;
f._initialize();
System.out.println(f.fib(n));
}
}
Табулирование (снизу вверх)
Табличная программа для данной задачи строит таблицу восходящим образом и возвращает последнюю запись из таблицы. Например, для одних и тех же чисел Фибоначчи мы сначала вычисляем fib(0), затем fib(1), затем fib(2), затем fib(3) и так далее. В буквальном смысле мы строим решения подзадач снизу вверх.
Ниже представлена табличная версия n-го числа Фибоначчи.
public static int fib(int n) {
int f[] = new int[n + 1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
Попробуйте ответить на следующие вопросы в качестве упражнения. 1) Напишите Memoized решение проблемы LCS (Самая длинная общая подпоследовательность). Обратите внимание, что табличное решение приведено в книге CLRS. 2) Как вы выбираете запоминание и табуляцию?
Tabulation vs Memoization
оптимальное основание
Заданная задача обладает свойством оптимальной подзадачи, если оптимальное решение данной задачи может быть получено с использованием оптимального решения подзадачи. Например, задача о кратчайшем пути имеет следующее свойство оптимальной подструктуры: если узел x находится на кратчайшем пути от исходного узла u к узлу назначения v, то кратчайший путь от u до v является кратчайшим путем от u до x и от x to Комбинация кратчайших путей для v. Стандартные алгоритмы кратчайшего пути для всех пар, такие как Флойда-Уоршалла и Беллмана-Форда, являются типичными примерами динамического программирования. Задача о самом длинном пути не имеет свойства оптимальной подструктуры.
Как решать задачи динамического программирования
шаг: Определите, является ли это проблемой dp ---> определите выражение состояния с наименьшим количеством параметров ---> определите взаимосвязь между различными состояниями ---> используйте табулирование или запоминание
Проблема dp обычно содержит состояние, то есть подзадачу, и ключом к ней является способ перехода между подсостояниями. Какой статус? Состояние можно определить как набор параметров, которые могут однозначно идентифицировать конкретное место или позицию в данной проблеме. Этот набор параметров должен быть как можно меньше, чтобы уменьшить пространство состояний.
Например: в нашей знаменитой задаче о рюкзаке мы определяем наше состояние двумя параметрами: индексом и весом, а именно DP[индекс][вес]. Здесь DP[индекс][вес] говорит нам, что максимальная прибыль, которую может получить предмет с возможностью упаковки в мешки от диапазона от 0 до индекса, является весом. Следовательно, метрики и веса параметров здесь могут однозначно идентифицировать подзадачи задачи о рюкзаке.
Итак, наш первый шаг — определить состояние проблемы после определения того, что проблема является проблемой DP.
Потому что мы знаем, что DP использует результат расчета для формулировки окончательного результата. Итак, наш следующий шаг — найти взаимосвязь между предыдущим состоянием и текущим состоянием. Эта часть является самой сложной частью решения проблемы DP и требует большого наблюдения и практики. Давайте разберемся, рассмотрев пример задачи
Учитывая 3 числа {1,3,5}, нам нужно сказать Мы можем составить общее количество чисел «N», Используйте сумму данных трех чисел. (Допускаются дубликаты и различные аранжировки).
Общее количество способов составить 6 равно: 8
1 + 1 +1 + 1 +1 + 1
1 + 1 +1 + 3
1 + 1 +3 + 1
1 + 3+ 1 + 1
3 + 1+ 1 + 1
3 + 3
1 + 5
5 + 1
dp[n] представляет общее количество перестановок, образующих n с использованием {1,3,5} в качестве элементов. Предположим, мы уже знаем dp[1],dp[2],dp[3]...,dp[6]. И мы хотим посчитать dp[7]. дп[7] = дп[7 - 1] + дп[7 - 3] + дп[7 - 5] дп[7] = дп[6] + дп[4] + дп[2] Итак, dp[n] = dp[n-1] + dp[n - 3] + dp[n - 5]
int solve(int n){
if(n < 0)
return 0;
if(n == 0)
return 1;
return solve(n-1) + sovle(n-3) + solve(n-5);
}
Adding memoization or tabulation for the state
// initialize to -1
int dp[MAXN];
// this function returns the number of
// arrangements to form 'n'
int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}
Tabulation vs Memoizatation
Метод табуляции – динамическое программирование снизу вверх
Как следует из самого названия, начните снизу и продвигайтесь к ответам вверху. Давайте обсудим с точки зрения переходов между состояниями. Опишем состояние задачи ДП как dp[x], где dp[0] — основное состояние, а dp[n] — целевое состояние. Итак, нам нужно найти значение целевого состояния, которое равно dp[n]. Если мы начинаем переход из основного состояния dp[0] и следуем нашему соотношению перехода состояния к нашему целевому состоянию dp[n], мы называем его восходящим подходом, потому что мы явно начинаем с самого нижнего состояния и достигаем оптимального состояния. .
Метод мемоизации — динамическое программирование сверху вниз
Мы начинаем с целевого состояния с наивысшим значением, и состояние может быть достигнуто путем вычисления целевого состояния для расчета его ответа, пока мы не достигнем нижней части основного состояния.
Решение задачи о рюкзаке с помощью динамического программирования
Каждый алгоритм динамического программирования начинается с сетки, и сетка для задачи о рюкзаке выглядит следующим образом:
Гитара стоит 1500, что соответствует 1 емкости, ноутбук стоит 2000, что составляет 3, а стоимость звука составляет 3000, что составляет 4.
Каждый ряд сетки — товар, а каждый столбец — рюкзак разной вместимости (от 1 до 4 фунтов).
- гитарный ряд
В первой ячейке указано, что рюкзак весит 1 фунт. Вес гитары также составляет 1 фунт, что означает, что она может загрузить рюкзак! Итак, это устройство содержит гитару и стоит 1500 долларов.
-
Аудио линия
Теперь вы находитесь на второй линии, а предметы, которые можно украсть, — это гитары и стереосистемы. В каждой строке предметы, которые можно украсть, — это предметы в текущей строке и предметы в предыдущих строках.
- Блокнот ряд
Эта же формула используется для расчета значения каждой ячейки. Формула выглядит следующим образом.
Код реализации задачи о рюкзаке:
Класс BagObject, представляющий объекты, загруженные в рюкзак.
public class BagObject {
public int capaticy;
public int value;
public BagObject(int cap, int val) {
// TODO Auto-generated constructor stub
this.capaticy = cap;
this.value = val;
}
}
public class PackageProblem {
private int cap;
private BagObject[] objs;
private int[][] dp;
public PackageProblem(int bagCap, BagObject[] objs) {
// TODO Auto-generated constructor stub
cap = bagCap;
this.objs = objs;
dp = new int[this.objs.length][cap];
}
public int getMaxValue() {
int nowval = objs[0].value;
int nowcap = objs[0].capaticy;
int i, j;
for (i = 0; i < cap; i++) {
if (i + 1 >= nowcap && dp[0][i] < nowval) {
dp[0][i] = nowval;
}
}
for (i = 1; i < this.objs.length; i++) {
nowcap = objs[i].capaticy;
nowval = objs[i].value;
for (j = 0; j < cap; j++) {
if (j + 1 - nowcap > 0) {
dp[i][j] = Math.max(dp[i - 1][j], nowval + dp[i - 1][j + 1 - nowcap]);
} else {
dp[i][j] = Math.max(dp[i - 1][j], nowval);
}
}
}
return dp[objs.length - 1][cap - 1];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BagObject guiter = new BagObject(1, 1500);
BagObject tap = new BagObject(3, 2000);
BagObject radio = new BagObject(4, 3000);
BagObject[] objs = new BagObject[3];
objs[1] = guiter;
objs[0] = tap;
objs[2] = radio;
PackageProblem pp = new PackageProblem(4, objs);
System.out.println(pp.getMaxValue());
}
}
Решение задач LCS с помощью динамического программирования
-
нарисовать стол
Рассмотрим три вопроса: Каково значение в ячейке? Как разделить эту проблему на подзадачи? Каковы оси сетки?
Значение в ячейке обычно является значением, которое вы хотите оптимизировать. В этом примере это:
两个字符串都包含的最长子串的长度.Допустим, сравним рыбу и хиш.
- формула
Ответ — наибольшее число в сетке.
самая длинная общая подпоследовательность
Количество букв, содержащихся в последовательности в обоих словах
код реализации
public class LongCS {
public static int lcs(String a, String b) {
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i < a.length() + 1; i++) {
for (int j = 1; j < b.length() + 1; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[a.length()][b.length()];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(lcs("AGGTAB", "GXTXAYB"));
}
}