原理入门理论最优化原理问题求解模式实现思路状态实现最长公共子序列凑硬币

原理

入门理论

最优化原理

1951年美国数学家R．Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优化原理”(PRinciple of optimality)：

“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。

这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件： (1) 问题中的状态必须满足最优化原理； (2) 问题中的状态必须满足无后效性。 所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。（这个感觉和马尔科夫模型很像） (3) 子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

问题求解模式

　　　　　 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 　　　　　 动态规划决策过程示意图 　　　　　

实现思路

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。现在让我们通过一个例子来了解一下DP的基本原理。首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

最重要的就是确定动态规划三要素： （1）问题的阶段 （2）每个阶段的状态 （3）从前一个阶段转化到后一个阶段之间的递推关系。

确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

举个例子：

http://www.VEVb.com/steven_oyj/archive/2010/05/22/1741374.html

实现思路有： 1.自顶向下(又称记忆化搜索、备忘录)：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算； 2.自底向上(递推)：从小范围递推计算到大范围； 动态规划的重点：递归方程+边界条件

动态规划算法可以求解很多问题，比如矩阵乘法、最长公共子序列、构造最优二叉查找树等，现就著名的最长公共子序列问题，采用动态规划法分析之。

状态

“状态”用来描述该问题的子问题的解。

实现

最长公共子序列

子序列:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij.

公共子序列:给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列.

最长公共子序列:给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列.

如：序列ABCDEF和ADFGH的最长公共子序列为ADF

注意:最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,简称LCS)的区别为是最长公共子串的串是一个连续的部分,而最长公共子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;通俗的说就是子串中字符的位置必须是连续的而子序列则可以不必连续。

问题描述：给定2个序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A},找出X和Y的最长公共子序列

1.分析最优子结构性质：

设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则

(1)若xm=yn,则zk=xm=yn,且z1,z2,…, zk-1是否为x1,x2,…,xm-1和y1,y2,…,yn-1的最长公共子序列.

(2)若xm≠yn且zk≠xm,则Z是x1,x2,…,xm-1和Y的最长公共子序列.

(3)若xm≠yn且zk≠yn,则Z是X和y1,y2,…,yn-1的最长公共子序列.

由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列.因此,最长公共子序列问题具有最优子结构性质.当问题具有最优子结构性质和子问题重叠性质时就可以用动态规划算法解决该问题.

2.由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系.用c[i][j]记录序列和的最长公共子序列的长度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.当i=0或j=0时,空序列是Xi和Yj的最长公共子序列.故此时C[i][j]=0.其它情况下,由最优子结构性质可建立递归关系如下: c[i][j]=⎧⎩⎨⎪⎪0,c[i−1][j−1]+1,maxc[i−1][j],c[i][j−1],if i=0,j=0if x>0,y>0, xi>yjif i>0,j>0,xi≠yj  $$c[i][j] = /begin{cases}0, & /text{if $i = 0, j =0$} //c[i - 1][j - 1] + 1, & /text{if $x > 0, y >0$, $x_i > y_j$} //max{c[i-1][j], c[i][j-1]}, & /text{if $i > 0, j > 0, x_i /neq y_j$ }/end{cases}$$

http://www.2cto.com/kf/201611/565606.html http://m.codes51.com/article/detail_556679.html

凑硬币

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)

首先我们思考一个问题，如何用最少的硬币凑够i元(i<11)？为什么要这么问呢？ 两个原因：1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。 2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的， 本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

好了，让我们从最小的i开始吧。当i=0，即我们需要多少个硬币来凑够0元。 由于1，3，5都大于0，即没有比0小的币值，因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便， 如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。那么， 我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0， 表示凑够0元最小需要0个硬币。当i=1时，只有面值为1元的硬币可用， 因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的， 即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时， 仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币， 接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里，你都可能会觉得，好无聊， 感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币！ 让我们看看i=3时的情况。当i=3时，我们能用的硬币就有两种了：1元的和3元的( 5元的仍然没用，因为你需要凑的数目是3元！5元太多了亲)。 既然能用的硬币有两种，我就有两种方案。如果我拿了一个1元的硬币，我的目标就变为了： 凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 这个方案说的是，我拿3个1元的硬币；第二种方案是我拿起一个3元的硬币， 我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是，我拿1个3元的硬币。好了，这两种方案哪种更优呢？ 记得我们可是要用最少的硬币数量来凑够3元的。所以， 选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。 我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。

上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的”状态”， 这个状态是怎么找出来的呢？我在另一篇文章 动态规划之背包问题(一)中写过： 根据子问题定义状态。你找到子问题，状态也就浮出水面了。 最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。 那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)， 上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错， 它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，

d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值。

伪代码为：

参考链接：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg http://www.hawstein.com/posts/dp-novice-to-advanced.html http://dev.21tx.com/2007/01/17/11010.html

动态规划与贪婪算法的区别：

http://www.programgo.com/article/67512173783/ http://amp.itgo.me/a/3219840973004004279

动态规划的教程算法以及源码：

http://www.xuebuyuan.com/zt/4352330.html https://www.codechef.com/wiki/tutorial-dynamic-programming