基本算法——动态规划算法

    动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

什么是动态规划

    动态规划（Dynamic Programming）对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算！

    动态规划是一种灵活的方法，不存在一种万能的动态规划算法可以解决各类最优化问题（每种算法都有它的缺陷）。所以除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，用灵活的方法建立数学模型，用创造性的技巧去求解。

基本策略

    基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

    动态规划中的子问题往往不是相互独立的（即子问题重叠）。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。

适用问题

那么什么样的问题适合用动态规划的方法来解决呢？

    适合用动态规划来解决的问题，都具有下面三个特点：最优化原理、最优化原理、有重叠子问题。

    如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。某阶段状态（定义的新子问题）一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与其以前的状态有关。子问题之间是不独立的（分治法是独立的），一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。

这类问题的求解步骤通常如下：

（1）分析最优解的性质，并刻画其结构特征，这一步的开始时一定要从子问题入手；

（2）定义最优解变量，定义递归最优解公式；

（3）以自底向上计算出最优值（或自顶向下的记忆化方式（即备忘录法））；

（4）根据计算最优值时得到的信息，构造问题的最优解。

1 事例一背包问题

问题描述：假设我们有n种类型的物品，分别编号为1, 2...n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是Cap。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？注意：每种物品只有一件，可以选择放或者不放。初始化数据为：n=5，w={2,2,6,5,4}，v={6,3,5,4,6}，Cap=10

解法如下：

A)描述最优解的结构

设子问题：f[i][v]表示允许前i件物品放入容量为v的背包时可以获得的最大价值。注：这里的i从0到5，v从0到10

为了能够得到已经计算过的，更小规模的子问题，我们可以根据当前限重来只考虑第i件物品放或者不放，那么就可以转化为涉及前i-1件物品的问题，

即：

情况1、如果第i件物品不能放（即这个物品的重量直接大于了当前限重v），则问题转化为“前i-1件物品放入容量为v的背包中”，即f[i-1][v]；

情况2、如果放第i件物品是可以放也可以不放，则问题转化为：

1）、如果选择不放第i件物品，则问题转化为“前i-1件物品放入容量为v的背包中”，即变大时f[i-1][v]；

2）、如果选择放第i件物品，则问题转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值w[i]。

则情况2下，f[i][v]的值就是1），2）中最大的那个值。

最优子结构描述如下：当子问题f[i][v]是最优时，其子问题f[i-1][v]和f[i-1][v-w[i]]（中的较大者）显然同样也必须是最优的值，不然在情况1或者情况2下总会矛盾。

B) 递归定义最优解的值

根据上面的分析，显然子问题

f[i][v]=f[i-1][v]，这时是情况1

f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i] }，这时是情况2。

C）按自底而上的方式计算最优解的值

2 事例二

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。

分析：动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上，我们让f(n)表示走上n级台阶的方法数。

那么当n为1时，f(n) = 1,n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。那么当我们要走上n级台阶，必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步，所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2)，我们用dp[n]来表示动态规划表，dp[i],i>0,i<=n,表示到达i级台阶的方法数。

3 事例三

给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

分析：对于这个题目，假设m是m行n列的矩阵，那么我们用dp[m][n]来抽象这个问题，dp[i][j]表示的是从原点到i,j位置的最短路径和。我们首先计算第一行和第一列，直接累加即可，那么对于其他位置，要么是从它左边的位置达到，要么是从上边的位置达到，我们取左边和上边的较小值，然后加上当前的路径值，就是达到当前点的最短路径。然后从左到右，从上到下依次计算即可。

4 事例四

给定两个字符串str1和str2，返回两个字符串的最长公共子序列，例如：str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最长公共子序列，返回哪一个都行。

分析：本题是非常经典的动态规划问题，假设str1的长度为M，str2的长度为N，则生成M*N的二维数组dp，dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。

dp值的求法如下：

dp[i][j]的值必然和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相关，结合下面的代码来看，我们实际上是从第1行和第1列开始计算的，而把第0行和第0列都初始化为0，这是为了后面的取最大值在代码实现上的方便，dp[i][j]取三者之间的最大值。

5 事例五

给定两个字符串str1，str2，在给定三个整数ic,dc,rc，分别代表插入，删除和替换一个字符的代价。返回将str1

编辑成str2的代价，比如，str1="abc",str2="adc",ic=5,dc=3,rc=2,从str1到str2，将'b'换成'd'代价最小，所以返回2.

分析：

在构建出动态规划表的时候，关键是搞清楚每个位置上数值的来源。首先我们生成dp[M+1][N+1]的动态规划表，M代表str1的长度，N代表str2的长度，那么dp[i][j]就是str1[0..i-1]变成str2[0...j-1]的最小代价，则dp[i][j]的来源分别来自以下四种情况：

a、首先将str1[i-1]删除，变成str1[0...i-2],然后将str1[0...i-2]变成str2[0...j-1],那么dp[i-1][j]就代表从str1[0..i-2]到str2[0...j-1]的最小代价，所以：dp[i][j] = dp[i-1][j]+dc;

b、同理也可以是从str1[0...i-1]变成str2[0...j-2]，然后在插入str2[j-1],dp[i][j-1]就代表从str1[0...i-1]变成str2[0...j-2]的最小大家，所以：dp[i][j] = dp[i][j-1]+ic;

c、如果str[i-1] == str2[j-1],则只需要将str1[0...i-2]变成str2[0...j-2]，此时dp[i][j] = dp[i-1][j-1];

d、如果str1[i-1]!=str2[j-1],则我们只需要将str1[i-1]替换成str2[j-1],此时dp[i][j] = dp[i-1][j-1]+rc;

在这四种情况当中，我们选取最小的一个，即为最小代价。