趣学算法之动态规划

14天阅读挑战赛
努力是为了不平庸~

算法知识点

动态规划算法的基本要素
（1）子问题重叠性质
每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题重叠性质。动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格（通常用二维数组）中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
（2）最优子结构性质——用动态规划法求解的前提。
当一个问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
一个问题的活动过程可以分为若干个阶段，每个阶段可包含一个或多个状态，从初始阶段的初始状态出发做出每个阶段的决策，形成一个决策序列。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式级时间，从而获得较高的解题效率。

算法题目来源

求两个给定序列X和Y的最长公共子序列

算法题目描述

求两个给定序列X和Y的最长公共子序列

做题思路

用动态规划算法求解问题的步骤：
1、找出最优解的性质，并刻划其结构特征；
2、递归地定义最优解值；
3、自底向上求最优解值；
4、根据计算最优解值时得到的信息构造一个最优解（此步只在要求得到最优解时才需要做）。
动态规划法是一种求解最优化问题的重要算法策略。

模板代码

class LCS
{
public:
LCS(int nx,int ny,char *x,char *y);
//创建二维数组c、s和一维数组a、b，并进行初始化
int LCSLength();//求最优解值（最长公共子序列长度）
void CLCS();//构造最优解（最长公共子序列）
…….
private:
void CLCS (int i, int j);
int **c,**s,m,n;//c[i][j]中保存最优解值
char *a,* b;
};
int LCS::LCSLength()//求最长公共子序列的长度
{
for (int i=1; i<=m; i++) c[i][0]=0;
for (i=1; i<=n; i++) c[0][i]=0;
for (i=1; i<=m; i++)//逐行向下
for (int j=1; j<=n; j++)//从左至右扫描求值
if (x[i]==y[j])
{  c[i][j]=c[i-1][j-1]+1; s[i][j]=1;
//由c[i-1][j-1]计算c[i][j]}
else if (c[i-1][j]>=c[i][j-1]
{  c[i][j]=c[i-1][j]; s[i][j]=2;
//由c[i-1][j]得到c[i][j]}
else 
{  c[i][j]=c[i][j-1]; s[i][j]=3;
//由c[i][j-1]得到c[i][j]}
return c[m][n];//返回最优解值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

做题过程中遇到的bug及解决方案

1、数组s可以省去
c[i][j]是由c[i][j]=c[i-1][j-1]+1，c[i][j]=c[i-1][j]或c[i][j]=c[i][j-1]计算得来的，要确定c[i][j]是从这三者中哪一个计算得来的，可以直接由c的值确定，而不必借助s。
因此可以写一个类似的CLCS算法在O(m+n)时间内构造最长公共子序列。
2、如果只需计算最长公共子序列的长度（而不用构造最优解），那么算法的空间需求还可以大大减少。
原因：计算c[i][j]仅用到第i行和第i-1行元素。因此只需两行元素空间就可以计算最长公共子序列的长度。
因此算法的空间复杂度为O(n)。

相关算法比较

动态规划法与分治法
共同点：
将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。
不同点：
1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；
而分治法中子问题相互独立。
2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；
而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。
动态规划法与贪心法
共同点：
都是求解最优化问题；都具有最优子结构性质。
不同点：
1、求解方式不同：
动态规划法：自底向上；
贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。
2、对子问题的依赖不同：
动态规划法：依赖于各子问题的解。只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；
贪心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择。

扩展

备忘录方法
备忘录方法的控制结构与自顶向下直接递归方法的控制结构相同。
区别在于备忘录方法为每个已解过的子问题建立了备忘录进行保存，以备需要时直接查看，之后不再重复计算。是动态规划法的一种变形。
备忘录方法与动态规划法比较
1、与动态规划法的共同点：用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算。
2、与动态规划法的区别：备忘录的递归方式是自顶向下，而动态规划法的递归方式是自底向上。
备忘录方法与递归方法比较
1、与递归方法的共同点：递归方式均为自顶向下
2、与递归方法的区别：备忘录方法用一个表格来保存已求解的子问题的答案，使下次需要解此子问题时，只简单地查看答案，不重新计算；而递归方法在每次遇到子问题都要重新计算。
如何选择使用动态规划法或备忘录法？
当一个问题的所有子问题都至少要解一次时，选用动态规划法较好，此时没有任何多余的计算，还可利用规则的表格存取方式，减少时间和空间需求。
当一个问题只有部分子问题需要求解时，选用备忘录法较好，它只解那些确实需要求解的子问题。