首页 > 代码库 > 浅显易懂的动态规划入门
浅显易懂的动态规划入门
为了引出动态规划的基本思想，请看下面的例子：
题目描述：
斐波那契数列是数学中常见的数列，也叫兔子数列，它满足：a[1]=1,a[2]=1,a[n]=a[n-1]+a[n-2](n>2),输入n，输出a[n] mod 10000007的值。(n<=100000)。
输入样例：
3
4
5
输出样例：
2
3
5
【算法分析】
看到题目以后，我们可以很轻松的写出两个版本的代码，一个是递推的代码，一个是递归的代码。其中，递归的代码如下：
/*
prob:fib-递归
author:aqx
lang:c++
*/
#include <iostream>
#define mod 10000007
using namespace std;
int f(int x)
{
if (x<=2)
return 1;
else
return (f(x-1)+f(x-2))%mod;
}
int main()
{
int n;
while (cin>>n)
{
cout<<f(n)<<endl;
}
}这一段代码看起来没有问题，但是运行起来却非常慢，当n=100的时候已经无法在有限的时间内得到结果，来看当n=5的例子：
当n=5的时候，使用递归的思路计算，f(3)被重复的调用了2次，f(2)被重复的调用了3次，而f(i)无论被调用多少次，它的返回值都是相同的，
因此，进行了很多次无用的计算。如果能够在第一次计算f(i)的时候，把f(i)的结果记录下来，下一次调用的时候，直接返回f(i)的值，就可以避免很多次冗余的计算。这样一来，把冗余的计算都省去，程序的效率得到了质的提升。
【程序实现】
/*
prob:fib-记忆化
author:aqx
lang:c++
*/
#include <iostream>
#define mod 10000007
using namespace std;
int a[100001];
int f(int x)
{
if (a[x]!=0) return a[x];
if (x<=2)
return a[x]=1;
else
return a[x]=(f(x-1)+f(x-2))%mod;
}
int main()
{
int n;
while (cin>>n)
{
cout<<f(n)<<endl;
}
}
斐波那契数列的求法，从严格意义上来说，可能并不算是动态规划，但是却和动态规划有着千丝万缕的联系：
1.利用多余的空间记录了重复状态的计算结果，避免了冗余的计算
2.有状态转移方程（在这里是f[i]=f[i-1]+f[i-2]，i>=3)
3.任何一个状态只与确定的前几项直接相关
动态规划中的一些常用名词的简单解释如下：
状态：状态是用来描述一个确定的自然状况或者是客观条件，例如在斐波那契数列中，每一个a[i]就是一个确定的状态。
阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。例如在斐波那契数列中，5和4就是一个阶段，5和3也是一个阶段。
无后效性：给定某一个状态，这个状态的结果只受它前一阶段的状态的影响，而不受到它前2、3…个阶段状态的影响。例如在斐波那契数列中，a[5]的值只受到a[4]和a[3]的影响，而不受到其他a[i]的影响。
决策：决策描述的是从一个状态转移到另一个状态的行动或者选择。例如，a[5]=a[4]+a[3]，这就是一种行动的过程。
状态转移：状态转移和决策很类似，它是描述在决策的过程中，两个状态之间的关系。例如在斐波那契数列中，a[i]=a[i-1]+a[i-2](i>2)，这就是一个状态转移方程。
以下是一道例题：
魔族密码（Vijos-p1028）
题目描述：
风之子刚走进他的考场，就……
花花：当当当当~~偶是魅力女皇——花花！！^^（华丽出场，礼炮，鲜花）
风之子：我呕……（杀死人的眼神）快说题目！否则……-_-###
花花：……咦~~好冷~~我们现在要解决的是魔族的密码问题（自我陶醉：搞不好魔族里面还会有人用密码给我和菜虫写情书咧，哦活活，当然是给我的比较多拉*^_^*）。魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表，每个单词至少包含1个字母，至多75个字母。如果在一个由一个词或多个词组成的表中，除了最后一个以外，每个单词都被其后的一个单词所包含，即前一个单词是后一个单词的前缀，则称词表为一个词链。例如下面单词组成了一个词链：
i
int
integer
但下面的单词不组成词链：
integer
intern
现在你要做的就是在一个给定的单词表中取出一些词，组成最长的词链，就是包含单词数最多的词链。将它的单词数统计出来，就得到密码了。
风之子：密码就是最长词链所包括的单词数阿……
花花：活活活，还有，这些文件的格式是，第一行为单词表中的单词数N（1<=N<=2000），下面每一行有一个单词，按字典顺序排列，中间也没有重复的单词咧！！你要提交的文件中只要在第一行输出密码就行啦^^看你长得还不错，给你一个样例吧：
输入样例：
5
i
int
integer
intern
internet
输出样例：
4
样例解释：
i->int->intern->internet
算法分析】
这道题目就是一道典型的线性动态规划，为了更好的理解它，我们首先来看它的搜索实现。如果用搜索算法来写这道题目，写起来是非常容易的，代码如下：
/*
prob:vijos-p1028-dfs
author:aqx
lang:c++
*/
#include <iostream>
#include <string.h>
using namespace std;
int n;
string s[2005];
int dp[2005];
int ans=0;
bool can(int i,int j)
{
if (i==0) return true;
if (s[j].find(s[i])==0) return true;
return false;
}
//i指的是当前搜索到了哪一个字符串，
//step指的是当前一共接了几个字符串
int dfs(int i,int step)
{
ans=max(ans,step);
for (int j=i+1;j<=n;j++)
if (can(i,j))
{
dfs(j,step+1);
}
return 0;
}
int main()
{
while (cin>>n)
{
ans=0;
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++)
{
cin>>s[i];
}
dfs(0,0);
cout<<ans<<endl;
}
}
但是这样的代码交上去只能得到90分。（在这个数据规模下能得到90分已经非常难得，实际竞赛中，这样的算法只能得到50分甚至更少）因此，其中必然存在着可以优化的内容。
看这样一个例子：
输入是：i,it,in,int,inter,internet
同样是inter结尾的单词序列，搜索的过程中会遇到有以下几种可能：
i->inter
in->inter
int->inter
i->in->inter
i->int->inter
in->int->inter
i->in->int->inter
他们都是以inter结尾的单词序列，之后能接的最长序列长度是一样的，假设从inter之后接出来的最长单词序列长度是x，而接到inter结尾的每一种情况的单词长度是a[i]的话，那么，每一种情况下的单词序列长度就是a[i]+x。对于本题，我们只关注最优解，而对于所有以inter结尾的单词序列，x都是相同的，那么，必然只有最大的a[i]才有可能产生最优解！其他的状态都是无用的，我们不应该去计算它！
因此，可以这样来定义一个状态：
dp[i]表示以第i个单词结尾的单词序列的最长长度。例如，dp[5]表示以inter结尾的单词序列中，最长的那一个序列的长度。显然，dp[5]=4。
之后，我们来考虑任何两个状态之间的联系：
对于一个dp[i]来说，哪些dp[j]和它相关呢？拿inter来举例子，以inter结尾的单词序列，只和i,in,int结尾的单词序列有关。更普遍的描述是：和i有关的每一个j满足：
1.j<i
2.s[j]是s[i]的前缀
当j可以接在i的前面时，dp[j]和dp[i]的联系，请看下面的图表：
i | 1 | 2 | 3 | 4 | 5 | 6 |
dp[i] | 1 | 1 | 2 | 3 | 4 | 5 |
对于dp[5],它与dp[1],dp[3],dp[4]都有联系，也就是说，以第5个字符串结尾的单词序列，可以由以第1、3、4个字符串结尾的单词序列接上第五个单词，组成更长的一个单词序列，因此：
dp[5]=dp[i]+1………………………………i=1,3,4
更普遍的：
dp[i]=dp[j]+1………………………………j<i且s[j]是s[i]的前缀
而我们只关心这其中最大的那一个，因此，需要在这个方程上做轻微的改动：
dp[i]=max(dp[i],dp[j]+1)………………………j<i且s[j]是s[i]的前缀
还需要注意初始状态：
dp[i]=1
因为每一个字符串自己也是一个单词序列。
有了初始状态、状态和状态转移方程，这就是一个完整的动态规划模型了。
动态规划的常用实现方式有递推和递归两种，本题使用递推的方式实现起来更容易，效率更高。
递推又分为顺推和逆推，本题将使用两种写法实现，方便读者更好的理解动态规划
/*
prob:vijos-p1028-逆推
author:aqx
lang:c++
*/
#include <iostream>
#include <string.h>
using namespace std;
int n;
string s[2005];
int dp[2005];
bool can(int i,int j)
{
if (s[j].find(s[i])==0) return true;
return false;
}
int main()
{
while (cin>>n)
{
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++)
{
cin>>s[i];
}
int ans=0;
//对任何一个i，枚举所有可以接在它之前的字符串j
for (int i=1;i<=n;i++)
{
dp[i]=1;
for (int j=1;j<i;j++)
if (can(j,i))
{
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
}
/*
prob:vijos-p1028-顺推
author:aqx
lang:c++
*/
#include <iostream>
#include <string.h>
using namespace std;
int n;
string s[2005];
int dp[2005];
bool can(int i,int j)
{
if (s[j].find(s[i])==0) return true;
return false;
}
int main()
{
while (cin>>n)
{
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++)
{
cin>>s[i];
}
int ans=0;
//对任何一个i，枚举它可以接在哪些字符串之前
for (int i=1;i<=n;i++)
{
if (dp[i]==0) dp[i]=1;
for (int j=i+1;j<=n;j++)
if (can(i,j))
{
dp[j]=max(dp[j],dp[i]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
}
两种实现方式略有不同，时间复杂度都是O（N2）
这道题本质上是一类非常典型的线性动态规划算法：最长上升子序列。最长上升子序列的模型是：一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。
实际上最长上升子序列还有更好的解法，此处暂不涉及。
浅显易懂的动态规划入门