动态规划专题

一些概念

· 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题地算法思想
· 动态规划将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解
· 一个问题必须拥有重叠子问题和最优子结构,才能使用动态规划去解决
· 分治与动态规划的区别:分治法分解出的子问题是不重叠的,分治法解决的问题不一定是最优化问题
· 贪心与动态规划:贪心以一种单链的流水方式进行,通过一种策略直接选择一个子问题去求解,没被选择的子问题就不去求解了,直接抛弃~

动态规划的递归写法

以求斐波那契数列为例,开一个一维数组dp[maxn]保存已经计算过的F[n]的值,并用dp[n]=-1表示当前还没被计算

1
2
3
4
5
6
7
8
int F(int n){
if(n==0||n==1) return 1;
if(dp[n]!=-1) return dp[n]; //已经计算过,直接返回结果
else{
dp[n]=F[n-1]+F(n-2);
return dp[n];
}
}

动态规划的递推写法

以数塔问题为例,自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//其决策式子为dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
//边界为最后一层dp[n][j]=f[n][j]
//最终结果就在dp[1][1]中
//边界
for(int j=1;j<=n;j++){
dp[n][j]=f[n][j];
}
//从第n-1层不断往上计算出dp[i][j]
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
//状态转移方程
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];
}
}

动态规划经典问题

最大连续子序列和

dp[maxn]中记录以当前下标为尾元素的最大和
A[i]必为当前子序列尾元素,于是状态转移方程可表述为:
dp[i]=max{A[i],dp[i-1]+A[i]};

1
2
3
4
5
6
7
8
9
//边界
dp[0]=A[0];
for(int i=1;i<n;i++)
dp[i]=max(dp[i-1]+A[i],A[i]);
int k=0;
for(int i=1;i<n;i++)
if(dp[i]>dp[k])
k=i;
//dp[k]中即为最大连续子序列和

插入概念:
· 状态的无后效性:当前状态记录了历史信息,一旦当前状态确定,就不会再改变,且未来的决策只能在已有的一个或若干个状态的基础上进行,历史信息只能通过已有的状态取影响未来的决策
· 并不是所有状态都具有无后效性,因此必须设计一个无后效性的状态以及相应的状态转移方程(这是动态规划的核心)
【PAT中对应题目:PATA1007 Maximum Subsequence Sum】

最长不下降子序列(LIS,Longest Increasing Sequence)

在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降(非递减)的
原始枚举方法下,每个元素都有取或不取两种情况,O(2^n),太大
动态规划做法:
· 令dp[i]表示以A[i]为结尾的最长不下降子序列长度,这样对A[i]有两种可能:
1.如果存在A[i]之前的元素A[j],使得A[j]<=A[i]且dp[j]+1>dpi,那么就把A[i]跟在A[j]结尾的LIS后面,形成一条更长的LIS(令dp[i]=dp[j]+1)
2.如果A[i]之前的元素都比A[i]大,那么A[i]只好自己形成一条LIS,长度为1

1
2
3
4
5
6
7
8
int ans=0;
for(int i=0;i<n;i++) {
for(int j=1;j<i;j++) {
if(A[i]>=A[j])
dp[i]=max(1,dp[j] + 1);
}
ans = max(dp[i], ans);
}

【PAT中对应可应用题目:1045 Favorite Color Stripe】

最长公共子序列(LCS,Longest Common Subsequence)

给定两个字符串(或数字序列)A和B,求一个字符串,求得这个字符串A和B的最长公共部分(子序列可以不连续)
动态规划做法:
· 令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度(下标从1开始?)
根据A[i]和B[j]的情况,分两种决策:
1.若A[i]==B[j],则字符串A与字符串B的LCS增加了1位,即有dp[i][j]=d[i-1][j-1]+1;
2.若A[i]!=B[j],则字符串A与字符串B的LCS无法延长,因此dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
边界:dp[i][0]==dp[0][j]=0(0<=i<=n,0<=j<=m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
gets(A+1);  //??gets 从下标为一开始读入
gets(B+1);
int lenA=strlen(A+1);
int lenB=strlen(B+1);
//边界
for(int i=0;i<=lenA;i++)
dp[i][0]=0;
for(int j=0;j<=lenB;j++)
dp[0][j]=0;
//状态转移方程
for(int i=1;i<=lenA;i++)
for(int j=1;j<=lenB;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]);
}
//dp[lenA][lenB]即答案

最长回文子串

给出一个字符串S,求S的最长回文子串。
暴力解法:端点枚举O(n^2),判断回文O(n),总共O(n^3)
如果把字符串S倒过来变成T,然后对T和S求LCS,这种想法事实上是错误的,因为一旦S中同时存在一个子串和他的倒序,那么答案就会出错。
动态规划做法:
· 令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串,是则为1,不是为0。这样根据S[i]是否等于S[j],可以把转移情况分为两类:
1.若S[i]==S[j],那么只要S[i+1]至S[j-1]是回文子串,S[i]至S[j]就是回文子串,如果S[i+1]至S[j-1]不是,则S[i]至S[j]也不是;即当S[i]==S[j]时,dp[i][j]=dp[i+1][j-1]
2.若S[i]!=S[j],那么dp[i][j]=0
边界:
dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0;
· 如果按i和j从小到大枚举子串的两个端点,然后更新dp[i][j],会无法保证dp[i+1][j-1]已经被计算过
· 可以先枚举子串长度L(L是可以取到整个字符串的长度S.len()的),再枚举左端点i,这样右端点i+L-1也可以直接得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
gets(S);
int len=strlen(S),ans=1;
//边界
for(int i=0;i<len;i++){
dp[i][i]=1;
if(i<len-1)
if(S[i]==S[i+1]){
dp[i][i+1]=1;
ans=2; //初始化时注意当前最长回文子串长度
}
}
//状态转移方程
for(int L=3;L<=len;L++){ //枚举子串长度
for(int i=0;i+L-1<len;i++){ //枚举子串的起始端点
int j=i+L-1; //子串右端点
if(S[i]==S[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
ans=L;
}
}
}
printf("%d",ans);

DAG最长路

(待)(看起来好难呀…)

01背包

有n件物品,每件物品的重量为w[i],价值为c[i]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品都只有一件
暴力枚举:每种物品都有放或不放两种选择,O(n^2)
动态规划做法:
· 令dp[i][v]表示前i件物品恰好装入容量为v的背包中所能获得的最大值。考虑堆第i件物品的选择策略,有两种情况:
1.不放第i件物品,那么问题转化为前i-1件物品恰好装入容量为v的背包中所能获得的最大价值,即的dp[i-1][v]
2.放第i件物品,那么问题转化为前i-1件物品恰好装入容量为v-w[i]的背包中所能获得的最大价值,即dp[i-1][v-w[i]]+c[i]
所以状态转移方程:
dp[i][v]=max{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}(1<=i<=n,w[i]<=v<=V)
边界:
dp[0][v]=0;

1
2
3
4
5
6
//二维
for(int i=1;i<=n;i++){
for(int v=w[i];v<=V;v++){
dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
}
}

优化空间复杂度(滚动数组):

1
2
3
4
5
6
//一维
for(int i=1;i<=n;i++){
for(int v=V;v>=w[i];v--){ //此处必须逆序枚举v
dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
}
}

· 第i件物品放或不放而产生的最大值是完全可以由前面i-1件物品的最大值来决定的,而暴力做法无视了这一点

完全背包

有n种物品,每种物品的单件重量为w[i],价值为从c[i]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品都有无穷件

1
2
3
4
5
6
//一维
for(int i=1;i<=n;i++){
for(int v=w[i];v<=V;v++){
dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
}
}