动态规划之线性动规

动态规划之线性动规

一、动态规划的基本概念

动态规划是一种用途很广的问题求解方法，它本身并不是一个特定的算法，而是一种思想，一种手段。

它的设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

几个专业术语:

1.多阶段决策问题:如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。（不同于贪心，贪心在当前阶段的决策确定以后，不会影响下一个阶段的决策）

2.阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

3.状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。

基本结构:

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

基本思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。可怜我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。


考虑且仅仅考虑由前一阶段状态转移到当前状态后，递推并选取出当前状态的最优解，具有无后效性和最优子结构的基本特征，无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。可怜

基本模型:

   适用动态规划的问题必须满足最优化原理和无后效性。

二、动态规划的分类

三、线性动规的相关问题

1.最长上升子序列

问题描述: 对于一串数A={a₁a₂a_3…a_n}_{，它的子序列为S=}{s₁s₂s_3…s_n}，满足{s₁<s₂<s₃<…<sm}。求A的最长子序列的长度。

eg:输入: 5 1 3 7 5 4

 输出:3

算法分析:

设d(i)是以i结尾的最长上升子序列的长度，则状态转移方程为

代码实现:

#include<stdio.h>
int max(int a,int b)
{return (a<b)?b:a;}
int main()
{int a[1010];int dp[1010];int n,i,j,ret;ret=1;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);    //读入数据dp[i]=1;             //初始化dp[]数组}for(i=1;i<=n;i++){for(j=1;j<i;j++){if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);    //转移状态方程}ret=max(ret,dp[i]);         }printf("%d",ret);return 0;
}

改进算法:

代码实现:

int search(int a[], int n, int t)
{int low = 1;int high = n;while (low <= high){int mid = (low + high) / 2;if (t == a[mid]){return mid;}else if (t > a[mid]){low = mid + 1;}else{high = mid - 1;}}return low;
}int dp(int a[], int m[], int n)
{int maxlen = 1;		//最长上升子序列的长度m[maxlen] = a[1];int i;for (i = 2; i <= n; i++){if (a[i] > m[maxlen]){m[++maxlen] = a[i];}else{//返回小于a[i]的最大值的位置pint p = dp(m, maxlen, a[i]);m[p] = a[i];}}return maxlen;
}

改进后的算法时间复杂度为O(nlogn)

最长上升子序列的变式:子弹拦截系统(最长非递增子序列)

问题描述:拦截导弹。导弹系统有缺陷，后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时，必须按照时间顺序，不允许先拦截后面的导弹再拦截前面的导弹。

输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数，表示第k枚导弹的高度，按时间顺序，空格分隔 

输出:每组输出一行，包含一个整数，表示能拦截多少导弹。 
输入: 
8 
300 207 155 300 299 170 158 65 
输出: 

6

算法分析:其实就是求最长非递增子序列（子序列中排在前面的数字不比排在后面的数字小，前面>=后面,降序）。递推关系为: F[1] = 1 

 F[i] = max{1,F[j]+1} | j < i && aj >= ai 

代码实现:

#include <stdlib.h>  
#include <string.h>  
#include <stdio.h>  
#define N 26  int max(int a,int b)  
{  return a > b ? a:b;  
}  int main(int argc,char* argv[])  
{  int iElemArr[N];//保存输入的元素  int iLenArr[N];//保存以第i号元素结尾的最长非递增子序列长度  int n,iCnt = 1;  int i,j;  while(EOF!=scanf("%d",&n))  {  //接受输入信息  int iTemp = n;  while(iTemp--)  {  scanf("%d",&iElemArr[iCnt++]);  }  //int iMax= 1;  //对每个元素进行遍历  for(i = 1 ; i <= n ; i++)  {  //易错，这里需要将初始值iMax放在每次i做变动之后  int iMax = 1;  //遍历当前元素之前的元素  for(j = 1; j < i ; j++)  {  //如果前面的元素>=后面的元素，就更新以第i个元素结尾的子序列的长度  if(iElemArr[j] >= iElemArr[i])  {  iMax = max(iMax,iLenArr[j] + 1);  }  }  iLenArr[i] = iMax;//更新以第i号元素结尾的子序列的长度  }  int iMMax = -123123123;  for(i = 1 ; i <= n ; i++)  {  if(iLenArr[i] > iMMax)  {  iMMax = iLenArr[i];  }  }  printf("%d\n",iMMax);  }return 0;
}

2.合唱队形

题目描述: 
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。

合唱队形定义：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，

则他们的身高满足T1 < T2 < … < Ti， Ti > Ti+1 > … > TK (1 <= i <= K)。 
要求：已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形

#include<stdio.h>  
#define maxStus 20  
int leftline(int*a,int line)  
{  int l[maxStus];  int t=0;  for(int i=0;i<line;i++)  {  l[i]=1;  for(int j=0;j<i;j++)  {  if(a[i]>a[j]&&l[i]<=l[j])  {  l[i]=l[j]+1;  }  }  if(l[i]>t)  {  t=l[i];  }  }  return t;  
}  
int rightline(int*a,int line,int n)  
{  int l[maxStus];  int t=0;  for(int i=line;i<n;i++)  {  l[i]=1;  for(int j=line;j<i;j++)  {  if(a[i]<a[j]&&l[i]<=l[j])  {  l[i]=l[j]+1;  }  }  if(l[i]>t)  {  t=l[i];  }  }  return t;  
}  
void computer(int*a,int n)  
{  int temp=0;  int max=0;  for(int i=1;i<n-1;i++)  {  temp=leftline(a,i)+rightline(a,i,n);  if(temp>max)  {  max=temp;  }  }  printf("%d\n",n-max);  
}  
int main()  
{  int n;  scanf("%d",&n);  int a[maxStus];  for(int i=0;i<n;i++)  {  scanf("%d",&a[i]);  }  computer(a,n);  
}  

3.剑客决斗

题目描述:

在路易十三和红衣主教黎塞留当权的时代，发生了一场决斗。n个人站成一个圈，依次抽签。抽中的人和他右边的人决斗，负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息，但“A赢了B”这种关系没有传递性。例如，A比B强，B比C强，C比A强。如果A和B先决斗，C最终会赢，但如果B和C决斗在先，则最后A会赢。显然，他们三人中的第一场决斗直接影响最终结果。假设现在n个人围成一个圈，按顺序编上编号1~n。一共进行n-1场决斗。第一场，其中一人（设i号）和他右边的人（即i+1号，若i=n，其右边人则为1号）。负者被淘汰出圈外，由他旁边的人补上他的位置。已知n个人之间的强弱关系（即任意两个人之间输赢关系）。如果存在一种抽签方式使第k个人可能胜出，则我们说第k人有可能胜出，我们的任务是根据n个人的强弱关系，判断可能胜出的人数。

样例输出

3

算法分析:编号为x的人能从所有人中胜出，必要条件是他能与自己“相遇”，即把环看成链，x点拆成两个在这条链的两端，中间的人全部被淘汰出局，x保持不败。这样，在连续几个人的链中，只须考虑头尾两个人能否胜利会师，中间的则不予考虑，从而少了一维状态表示量。设meet[i,j]记录i和j能否相遇，能相遇则为true，否则为false。状态转移方程为:meet[i][j]=meet[i][k]&&meet[k][j]&&i能战胜k或者j能战胜k  其中meet[i][j]表示编号i，j战士可相遇。或者这样理解，不要纠结于谁赢谁输，只要本人能和本人决斗，则说明此人胜出，以此为突破点。

代码实现:

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
using namespace std;  
int dp[505][505];  
int vic[505][505];  
int main()  
{  int T;  scanf("%d",&T);  while(T--)  {  int n;  scanf("%d",&n);  for(int i=0;i<n;i++)  for(int j=0;j<n;j++)  scanf("%d",vic[i]+j);  memset(dp,0,sizeof(dp));  for(int i=0;i<n;i++)  dp[i][(i+1)%n]=1;//只有相邻的两个人能够决斗  int end1;  for(int i=1;i<n;i++)//决斗的两人之间相邻的人数  for(int start=0;start<n;start++)  {  end1=(start+i+1)%n;  if(vic[start][end1])//如果可以胜出，则不用讨论  {  continue;  }  for(int j=(start+1)%n;j!=end1;j++,j%=n)  {  //start能和jPK并且，end1能和j，并有一方能把jPK掉，那么start就能和end1PK  if(dp[start][j]&&dp[j][end1]&&(vic[start][j]||vic[end1][j]))  {  dp[start][end1]=1;  }  }  }  int count1=0;  for(int i=0;i<n;i++)  if(dp[i][i])  count1++;  printf("%d\n",count1);  }  return 0;  
}  

4.挖地雷

题目描述:在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入输出格式

输入文件mine.in有若干行。

第1行只有一个数字，表示地窖的个数N。

第2行有N个数，分别表示每个地窖中的地雷个数。

第3行至第N+1行表示地窖之间的连接情况：

第3行有n-1个数（0或1），表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为1 1 0 0 0 … 0，则表示第1个地窖至第2个地窖有路径，至第3个地窖有路径，至第4个地窖、第5个、…、第n个地窖没有路径。

第4行有n-2个数，表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。

… …

第n+1行有1个数，表示第n-1个地窖至第n个地窖有否路径连接。（为0表示没有路径，为1表示有路径）。

输出文件wdl.out有两行数据。

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例

5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

1 3 4 5
27

算法分析:详见代码注释部分，先上状态转移方程供参考:dp方程：if(f[i][j]==1&&dp[i]<dp[j]+w[i])dp[i]=dp[j]+w[i];\\j>i

代码实现:

#include<iostream>#include<cstring>#define MAXN 200using namespace std;bool a[MAXN][MAXN];//a[i][j]表示第i个地窖和第j个地窖是否是通路int w[MAXN];//每个地窖的地雷数int f[MAXN];//f[i]表示从第i个地窖开始挖的最多地雷数int suf[MAXN];int main(){memset(a,0,sizeof(a));memset(w,0,sizeof(w));memset(f,0,sizeof(f));long n,i,j,x,y,l,k,maxn;cin>>n;for(i=1;i<=n;i++){cin>>w[i];}while(cin>>x>>y){if(x==0&&y==0) break;a[x][y]=true;}f[n]=w[n];//初始状态for(i=n-1;i>=1;i--){l=0,k=0;for(j=i+1;j<=n;j++){if((a[i][j])&&f[j]>l){l=f[j];k=j;}}f[i]=w[i]+l;suf[i]=k;} k=1;for(i=1;i<=n;i++)//从n个数中找最大值{if(f[i]>f[k]) k=i;}maxn=f[k];cout<<k;//先输出起始点k=suf[k];while(k!=0)//向后的链表{cout<<"-"<<k;k=suf[k];}cout<<endl;cout<<maxn<<endl;return 0;} 

5.建学校

题目描述:政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。
已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。
为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。

请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

输入
第1行为m和n，其间用空格间隔
第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如
10 3
2 4 6 5 2 4 3 1 3
表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。
输出
各村庄到最近学校的距离之和的最小值。
样例输入
10 2
3 1 3 1 1 1 1 1 3
样例输出

18

算法分析:根据题意，我们可以把这些村庄间的道路连成了一条长链。想象一下这条链从左到右延伸，上面的某些结点已经建了学校，我们在这些结点的右侧找一个结点a，建一个新的学校。
新学校管辖的结点范围有多大呢？
结点a右边的村庄全部应该受a学校管辖，结点左边的学校则需要枚举判断了。
在决策结点a的学校之前，我们应该已经决策了另外一些已建好的学校，它们的决策方式和上面是相同的。
假设我们已经决策过i-1个村庄是否建了学校，正在决策第i个，之前建好的学校管辖范围是1~k，那么新学校的管辖范围应该是k+1~m，（k的范围是"已有学校数"~m-1）
        设f[决策的村庄数][建的小学数]=题目要求的距离，s[管辖区起点][管辖区终点]=这片辖区内建一个学校，区内村庄到学校的距离和。

f[i][j]=min(f[i][j],f[k][j-1]+s[k+1][i])

代码实现:

#include<stdio.h>
#include<math.h>
int min(int a,int b)  {return(a<b)?a:b;}

int dp[510][510],d[510][510],a[510];
int sum(int i,int j){//建一所学校的最小距离之和 int mid=(i+j)/2,l,ans=0;for(l=i;l<=j;l++){ans+=abs(a[l]-a[mid]);}return ans;
}int main(){int i,j,k,n,m;scanf("%d%d",&m,&n);for(i=2;i<=m;i++){scanf("%d",&a[i]);a[i]+=a[i-1];}//i到j之间建一所学校的最小距离 for(i=1;i<=m;i++){for(j=i;j<=m;j++){d[i][j]=sum(i,j);}}//将已知的dp求出 dp[0][0]=0;for(i=1;i<=m;i++){dp[i][1]=d[1][i];}//动态规划 for(i=n;i<=m;i++){for(j=2;j<=n&&j<=i;j++){//j=1时dp[i][j]=d[1][i];dp[i][j]=dp[i-1][j-1];for(k=i-2;k>=j-1;k--){dp[i][j]=min(dp[i][j],dp[k][j-1]+d[k+1][i]);}}}printf("%d",dp[m][n]);
}

四、线性dp小结

1.最长字段和(话不多说，直接上dp转移方程代码)

for(int i=2;i<=n;i++){if(dp[i-1]>=0)dp[i]=dp[i-1]+a[i];elsedp[i]=a[i];}

升级版:(二维):求最大子矩阵和

状态转移方程，其实就是将一维转换成二维的，如何转换呢？操作就是将第一行每个数加上第二行对应的每个数，变成一维的进行dp,再加上第三行对应的每个数，进行DP。起点行分别枚举从1到n。

代码如下:

 for(int i=1;i<=n;i++){memset(b,0,sizeof(b));memset(dp,0,sizeof(dp));for(int k=i;k<=n;k++){for(int j=1;j<=n;j++){b[j]+=a[k][j];if(dp[j-1]>=0)dp[j]=dp[j-1]+b[j];elsedp[j]=b[j];if(sum<dp[j])sum=dp[j];}}}

2.LIS问题(LIS就是最长下降子序列或者是最长上升子序列)有O(n^2)效率的算法，也有O(nlogn)效率的算法。其实过程很简单，以最长上升子序列为例。dp数组的最终长度就是最长上升子序列，遍历a数组，a[i]如果比dp数组最后一个元素大，即a[i]>dp[len]则直接加入dp数组里。否则就要二分查找到第一个小于a[i]的dp[j],然后将dp[j]换成a[i],最终的dp数组的长度就是答案。 (详见前文)

3.LCS问题(最长公共子序列问题)(还是写一下详细的分析流程吧)

定义状态：（这里还是假设求的是两个串的LCS）
dp[i][j]:定义为a串第i位置b串第j位置以前的两个序列的最大的LCS，那么显而易见，dp[0][0]=0,dp[n][m]就是我们要求的最大值
状态转移方程：
1.a[i]=b[j]   dp[i][j]=dp[i-1][j-1]+1
2.a[i]!=b[j]   dp[i][j]=max(dp[i-1][j],dp[i][j-1])
对于上面的状态转移方程的解释：
当i，j位置的字符匹配的时候，我们i，j位置以前的LCS就是i-1，j-1位置以前的LCS的长度+1

当i，j位置的字符不匹配的时候，那么LCS的长度是不会增加的，但是我们有两种选择，就是i，j-1位置以前的和i，j-1位置以前的，我们选取最大的LCS作为当前的LCS即可

PS:附图一张（从别人博客盗来的）便于理解

核心代码如下:

for(int i=1;i<=n;i++)  
{  for(int j=1;j<=m;j++)  {  if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;  else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);  }  
}   print dp[n][m]