Суть динамического программирования
Пять часто используемых алгоритмов включают динамическое программирование, разделяй и властвуй, жадное решение, поиск с возвратом и метод ветвления и ограничения.
Динамическое программирование — это не столько алгоритм, сколько идея решения проблем. :peach:
Dynamic Programming is a methed for solving a complex problem by breaking it down into a collection of simpler subproblems.
Приведенная выше цитата из Википедии означает, что динамическое программирование — это метод разложения сложной проблемы на несколько простых наборов задач.
Итак, как декомпозировать проблему, становится сутью динамического программирования.
Проблема разложения зависит отстатус проблемыипереходы между состояниями.
- Как определить состояние
Нам нужно найти проблему в определенном состоянииОптимальным решением. :strawberry:
Например:
самая длинная возрастающая подпоследовательность (LIS) Для заданного массива длины N найдите самую длинную монотонную самовозрастающую подпоследовательность (не обязательно непрерывную, но порядок не может быть нарушен) Пример: Дан массив A{5, 6, 7, 1, 2, 8} длины 6. Тогда его самая длинная монотонно возрастающая подпоследовательность есть {5, 6, 7, 8} длины 4
Отсюда мы определяем состояние, когда самая длинная возрастающая подпоследовательность dp(i) заканчивается i-м элементом массива. ЛИС всего массива — это максимальное значение dp(1)...dp(n).
Исходя из этого, мы определили состояние проблемы, и теперь мы рассмотрим переход между различными состояниями.
- Как найти переходы между состояниями
Во-первых, нам нужно найти состояниеГраничное значение. :watermelon:
Согласно приведенной выше задаче LIS, граничное значение равно 1, когда i=1, а самая длинная возрастающая подпоследовательность равна 1.
Затем нам нужно найти разницу между состояниямисвязь. :banana:
dp(i) = max(1,dp(j)+1...) (0<=j<i) 当array[j]<array[i]
Объясните, в случае, если i-й элемент гарантированно больше, чем j-й элемент, берется максимальное значение самой длинной возрастающей подпоследовательности всех предыдущих элементов плюс 1.
Здесь видно, что уравнение перехода состояния здесь определяет связь между проблемой и подзадачами. Видно, что уравнение перехода состояния представляет собой рекуррентную формулу с условием.
Классические упражнения по динамическому программированию
Вот 6 наиболее классических упражнений по динамическому программированию. :corn:
/**
* No1.塔树选择和最大问题
*
* 一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
* 每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
* 5
* 8 4
* 3 6 9
* 7 2 9 5
* 例子中的最优方案是：5 + 8 + 6 + 9 = 28
*
* 输入：符合塔树的二维数组。
* 输出：经过的最大值。
*/
/**
* No2.∑乘法表问题
*
* ∑ | a b c
* ——————————————
* a | b b a
* b | c b a
* c | a c c
*
* 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。
* 例如,对于字符串x=bbbba,它的其中一个加括号表达式为i(b(bb))(ba)。
* 依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn。
* 计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。
*
* 输入：输入一个以a,b,c组成的任意一个字符串。
* 输出：计算出的加括号方式数。
*/
/**
* No.3跳台阶
*
* 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
* 求该青蛙跳上一个n级的台阶总共有多少种跳法。
*
* 输入：台阶数n。
* 输出：跳法总数。
*/
/**
* No.4最长递增子序列(LIS)
*
* 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。
* 例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}。
* 则其最长的单调递增子序列为{5，6，7，8}，长度为4。
*
* 输入：一个数组。
* 输出：最长递增子序列的长度。
*/
/**
* No.5背包问题
*
* 有N件物品和一个容量为V的背包。
* 第i件物品的大小是c[i]，价值是w[i]。
* 求解将哪些物品装入背包可使价值总和最大。
*
* 输入：物品大小数组c,物品价值数组w,背包容量。
* 输出：最大的价值。
*/
/**
* No.6最长公共子序列(LCS)
*
* 给出两个字符串a, b，求它们的最长的公共子序列。
*
* 输入：字符串a和字符串b。
* 输出：最长的公共子序列的长度。
*/
Во-первых, в соответствии с характером динамического программирования определитегосударствоиотношения между государствами, а затем написать код.
Если вы выполнили упражнение, вот ответы на приведенные выше вопросы,кликните сюда.
Поделитесь хорошим пониманием динамического программирования.