1. Введение в динамическое программирование
Динамическое программирование — это метод оптимизации, используемый в информатике и математике для решения проблем путем их разбиения на более мелкие, перекрывающиеся подзадачи, которые можно решать независимо друг от друга. Этот метод особенно полезен для решения задач с оптимальной структурой и перекрывающимися подзадачами, которые являются ключевыми характеристиками задач динамического программирования.
2. Ключевые термины
- Оптимальная подструктура: проблема имеет оптимальную подструктуру, если ее оптимальное решение может быть эффективно построено из оптимальных решений ее подзадач.
- Перекрывающиеся подзадачи: проблема имеет перекрывающиеся подзадачи, если одна и та же подзадача решается несколько раз при решении более крупной проблемы.
3. Определение проблемы динамического программирования
Проблема может быть идентифицирована как задача динамического программирования, если она обладает следующими свойствами:
- Оптимальная подструктура: проблема может быть разбита на более мелкие подзадачи, и оптимальное решение исходной задачи может быть определено из оптимальных решений этих более мелких подзадач.
- Перекрывающиеся подзадачи: проблема имеет подзадачи, которые решаются несколько раз. Это свойство позволяет нам экономить время вычислений, запоминая или кэшируя результаты этих подзадач.
4. Шаги для решения задачи динамического программирования
- Определите, демонстрирует ли проблема оптимальную подструктуру и перекрывающиеся подзадачи.
- Определите структуру проблемы и желаемый результат.
- Разбейте проблему на более мелкие, пересекающиеся подзадачи.
- Создайте таблицу запоминания для хранения результатов подзадач, чтобы избежать избыточных вычислений.
- Напишите рекурсивное решение задачи, используя таблицу запоминания.
- Преобразуйте рекурсивное решение в итеративное, если это возможно, для повышения производительности.
5. Примеры задач динамического программирования
5.1 Числа Фибоначчи
Последовательность Фибоначчи — это ряд чисел, где каждое число является суммой двух предыдущих, обычно начиная с 0 и 1. Последовательность идет 0, 1, 1, 2, 3, 5, 8, 13 и так далее.
Рекурсивное решение без динамического программирования
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Рекурсивное решение с динамическим программированием (мемоизация)
public static int fibonacci(int n, int[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] == 0) {
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
}
return memo[n];
}
Итеративное решение с динамическим программированием (снизу вверх)
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
5.2 Самая длинная общая подпоследовательность
Проблема самой длинной общей подпоследовательности (LCS) заключается в поиске самой длинной подпоследовательности, которая существует в обеих входных последовательностях. Подпоследовательность — это последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка оставшихся элементов.
Рекурсивное решение без динамического программирования
public static int lcs(String s1, String s2, int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
return 1 + lcs(s1, s2, m - 1, n - 1);
} else {
return Math.max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}
}
Рекурсивное решение с динамическим программированием (мемоизация)
public static int lcs(String s1, String s2, int m, int n, int[][] memo) {
if (m == 0 || n == 0) {
return 0;
}
if (memo[m][n] != -1) {
return memo[m][n];
}
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
} else {
memo[m][n] = Math.max(lcs(s1, s2, m, n - 1, memo), lcs(s1, s2, m - 1, n, memo));
}
return memo[m][n];
}
Итеративное решение с динамическим программированием (снизу вверх)
public static int lcs(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (s1.charAt(i - 1) == s2.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[m][n];
}
5.3 Задача о рюкзаке 0/1
Учитывая набор предметов, каждый из которых имеет вес и ценность, задача о рюкзаке 0/1 состоит в том, чтобы определить максимальную ценность, которую можно положить в рюкзак фиксированной вместимости. Каждый предмет можно использовать не более одного раза.
Рекурсивное решение без динамического программирования
public static int knapSack(int W, int[] wt, int[] val, int n) {
if (n == 0 || W == 0) {
return 0;
}
if (wt[n - 1] > W) {
return knapSack(W, wt, val, n - 1);
} else {
return Math.max(val[n - 1] + knapSack(W - wt[n -1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
}
}
Рекурсивное решение с динамическим программированием (мемоизация)
public static int knapSack(int W, int[] wt, int[] val, int n, int[][] memo) {
if (n == 0 || W == 0) {
return 0;
}
if (memo[n][W] != -1) {
return memo[n][W];
}
if (wt[n - 1] > W) {
memo[n][W] = knapSack(W, wt, val, n - 1, memo);
} else {
memo[n][W] = Math.max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1, memo),
knapSack(W, wt, val, n - 1, memo));
}
return memo[n][W];
}
Итеративное решение с динамическим программированием (снизу вверх)
public static int knapSack(int W, int[] wt, int[] val) {
int n = val.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (wt[i - 1] <= w) {
dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
6. Заключение
Динамическое программирование — это мощная техника, которая помогает решать сложные проблемы, разбивая их на более мелкие, перекрывающиеся подзадачи. Распознав оптимальную подструктуру и перекрывающиеся подзадачи в данной задаче, можно применить динамическое программирование для достижения эффективных решений. Примеры, представленные в этом руководстве, демонстрируют, как выявлять, анализировать и решать проблемы динамического программирования с помощью Java. Не забывайте практиковаться с разными задачами, чтобы освоить этот подход.
