动态规划的理解与案例分析

动态规划的本质

常用的五大算法，包含 动态规划、分治法、贪心求解法、回朔法、分支限界法。

动态规划(Dynamic Programming)，与其说是一种算法，不如说是一种解决问题的思路。 :peach:

Dynamic Programming is a methed for solving a complex problem by breaking it down into a collection of simpler subproblems.

上述引自维基百科，也就是说动态规划就是将一个复杂的问题分解成若干简单的问题集的一种方法。

那么怎么分解问题就成了动态规划的本质。

而分解问题，依靠的就是 问题的状态 和 状态之间的转移。

1. 如何定义一个状态

我们需要找到一个问题在某一个状态的 最优解。 :strawberry:

举个例子：

最长递增子序列(LIS) 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱） 例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8} 则其最长的单调递增子序列为{5，6，7，8}，长度为4

由此我们定义一个状态，当以第i个数组元素结尾的最长递增子序列dp(i)。 整个数组的LIS就是dp(1)...dp(n)的最大值。

由此我们就定义好了一个问题的状态，下面我们就看看不同状态之间的转移。

2. 如何找到状态的转移

首先，我们需要找到状态的 边界值。 :watermelon:

根据上述LIS的问题，边界值为当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。* 输出：最长的公共子序列的长度。*/
复制代码

请先根据动态规划的本质，定义出 状态 和 状态之间的关系，然后再进行代码编写。

如果你已经完成了练习，这里有上述问题的答案，戳这里。

分享一个对于动态规划比较不错的理解。