文章目录
  1. 1. 最长上升子序列
    1. 1.1. 性质
    2. 1.2. 二分复杂度优化 O(nlogn)
    3. 1.3. 例题1:拦截导弹
    4. 1.4. 例题2:最少拦截系统
    5. 1.5. 例题3:Wooden Sticks
  2. 2. 最长公共子串(dp) O(n^2)
  3. 3. 最长公共子序列 O(n^2)
  4. 4. 最长公共上升子串 O(n^2)
  5. 5. 最长公共上升子序列 O(n^2)
    1. 5.1. 变式:最长公共连续上升子序列
      1. 5.1.1. 题目要求
      2. 5.1.2. 解题思路
  6. 6. 最大子段和
    1. 6.1. 算法1:分治策略递归求解 O(nlogn)
    2. 6.2. 算法2:动态规划求解 O(n)
  7. 7. 最大M子段和 O(n^2)
  8. 8. 钱币兑换问题
    1. 8.1. 找规律与公式
    2. 8.2. DP角度
      1. 8.2.1. 整数拆分问题
      2. 8.2.2. 另一种方法
  9. 9. DP总结:针对一个DP问题该如何思考
    1. 9.1. 如何确定dp候选变量
      1. 9.1.1. 考虑问题规模作为变量
      2. 9.1.2. 在思考如何转移时引入变量
    2. 9.2. 如何进行转移,以及确定dp变量
    3. 9.3. 考虑非法转移点
    4. 9.4. 考虑初始点

本文涉及:

  • DP总结:针对一个DP问题该如何思考(见文末)
  • 最长上升子序列,二分优化及变形
  • 最长公共子串
  • 最长公共子序列
  • 最长公共上升子串
  • 最长公共上升子序列
  • 最大子段和
  • 最大M子段和

文章创建于2017年08月10日,经过多次更新。


最长上升子序列

性质

  • Dilworth定理:最长上升子序列的长度等于非上升子序列的最小划分个数(划分是指不重叠,最小划分含义为划分个数不能再少了)

    相似的,最长非下降子序列的长度等于下降子序列的最小划分个数,最长下降子序列的长度等于非下降子序列的最小划分个数……

    简单证明见下面例题2。

  • 参考:https://blog.csdn.net/xuzengqiang/article/details/7266034

  • 一个反链A是X的一个子集,它的任意两个元素都不能进行比较。

    一个链C是X的一个子集,它的任意两个元素都可比。

  • 定理1 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。

  • 定理2 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

二分复杂度优化 O(nlogn)

  • 最长上升子序列STL二分模板(非严格递增改为upper_bound):
1
2
3
4
5
6
7
8
9
10
11
int LIS()
{
memset(dp,INF,sizeof(dp));
for(int i=0;i<n;i++)
{
int *p=lower_bound(dp,dp+n,a[i]);
*p=a[i];
maxlen[i]=p-dp+1;//存储以a[i]为尾元素的最长上升子序列的长度
}
return lower_bound(dp,dp+n,INF)-dp;
}
  • 最长 ?? 子序列STL二分模板全家桶:
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
#include<cstring>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int dp[10001];
int maxlen[10001];
int a[10001] = { 9,9,2,5,5,4 };
template<class comp>
int LS(int *a, int n, comp cmp, int INIT)
{
int maxl = 0;
memset(dp, INIT, sizeof(dp));
for (int i = 0; i<n; i++)
{
int *p = lower_bound(dp, dp + n, a[i], cmp);
*p = a[i];
maxlen[i] = p - dp + 1;//存储以a[i]为尾元素的最长子序列的长度
maxl = max(maxl, maxlen[i]);
}
return maxl;
}
int main(void)
{
cout << LS(a, 6, less<int>(), INF) << endl;//严格上升
cout << LS(a, 6, less_equal<int>(), INF) << endl;//非严格上升
cout << LS(a, 6, greater<int>(), -INF) << endl;//严格下降. 在降序数组中查找第一个匹配(精准覆盖)
cout << LS(a, 6, greater_equal<int>(), -INF) << endl;//非严格下降. 在降序数组中查找最右匹配+1(避免覆盖)
return 0;
}
  • 开辟一个新数组,在里面顺次对每个元素进行二分查找并填充元素,填充的位置+1即以该元素结尾的最长子序列长度。
  • 注意,在排序时,greater是升序排序;在查找时,greater适用于降序数组。
  • 以下例题都是O(n2)O(n^2)的做法,都可以用模板优化。

例题1:拦截导弹

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
31
32
33
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[10001];
int dp[10000];
int solve(int *a,int n)
{
int maxn=0;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]<=a[j])//注意,此题求的是可拦截的最大导弹,因此应该是求最长非升子序列
dp[i]=max(dp[i],dp[j]+1);
}
maxn=max(maxn,dp[i]);
}
return maxn;
}

int main(void)
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",solve(a,n));
}
return 0;
}

例题2:最少拦截系统

  • 这是一道性质的应用。让求非升子序列的最小划分,那么到底等不等于最长上升子序列的长度呢?

    https://blog.csdn.net/litble/article/details/85305561

    如果有a是导弹抵达时间,b是高度,那么定义偏序关系为a1<a2且b1>=b2,求该偏序关系上的链的最小划分,即求反链的最大集合长度。

    证明:反链即这样的一个集合,该集合上任意两个元素都不满足偏序关系,即任意两个导弹都不满足(a1<a2且b1>=b2)或(a2<a1且b2>=b1),即任意两个导弹都要满足(a1>=a2或b1<b2)且(a2>=a1或b2<b1),即任意两个导弹都要满足(a1>=a2或b1<b2)且(a1<=a2或b1>b2)。当a1==a2时成立,但由于没有两个导弹会同时到达,因此a1==a2的情况排除;当a1!=a2时,需要满足(a1>a2且b1>b2)或(a1<a2且b1<b2),显然等价于严格上升关系。

    所以应求最长上升子序列的长度。

  • 传送门:HDU - 1257

  • AC代码

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
31
32
33
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#define max(x,y) ((x)>(y)?(x):(y))
int dp[10000];
int a[10001];
int LIS(int *a,int n)
{
int maxn=0;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
}
maxn=max(maxn,dp[i]);
}
return maxn;
}
int main(void)
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",LIS(a,n));
}
return 0;
}

例题3:Wooden Sticks

  • 这是一道性质的应用,如果用二分优化复杂度可以优化到O(nlogn)O(nlogn)。当然也可以贪心去做。
  • 这道题是求非降子序列的最小划分,即求下降子序列的最大长度。二分优化使用greater<int>()​
  • 传送门:HDU - 1051
  • AC代码:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
typedef long long ll;
using namespace std;
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
struct s
{
int a,b;
}st[10010];
bool cmp(s a,s b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
int dp[10010],n;
int LDS()
{
for(int i=0;i<n;i++)
dp[i]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(st[j].b>st[i].b)
dp[i]=max(dp[i],dp[j]+1);
}
}
int m=0;
for(int i=0;i<n;i++)
m=max(dp[i],m);
return m;
}
int main(void)
{
int T=read();
while(T--)
{
n=read();
for(int i=0;i<n;i++)
{
st[i].a=read();
st[i].b=read();
}
sort(st,st+n,cmp);
/*for(int i=0;i<n;i++)
printf("%d,%d\n",st[i].a,st[i].b);*/
printf("%d\n",LDS());
}
return 0;
}

最长公共子串(dp) O(n^2)

  • 对了,这个做法是O(n2)O(n^2)的,但是用后缀数组+高度数组可以降到O(nlogn)O(nlogn )这里不提。

  • 附上滚动数组DP代码(下标从1开始):

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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[210];
int main()
{
char s1[]=" ider.cs@gmail.com";
char s2[]=" blog.iderzheng.com";
int len1=strlen(s1),len2=strlen(s2);
int maxn=0;
for(int i=1;i<len1;i++)
{
dp[0]=0;
for(int j=len2-1;j>=1;j--)
{
if(s1[i]==s2[j])
dp[j]=dp[j-1]+1;//注意内层循环的方向
else
dp[j]=0;//丢掉之前的状态不保留
}
for(int j=1;j<len2;j++)
printf("%d ",dp[j]);
putchar('\n');
}
printf("%d\n",maxn);
return 0;
}

代码中需要注意的是内层循环需要从右向左进行,这样才能不损失dp[j-1]这个状态。

最长公共子序列 O(n^2)

  • 这个无疑是最长公共子串的升级版了,可以对比来学习。

  • 参考博文:最长公共子序列(LCS)问题 ,先上这个很经典的图:

  • 从图中很清楚可以看到和最长公共子串的区别在于,它是:

    • 如果str1[m] == str2[n],则L[m,n] = L[m - 1, n -1] + 1 ;
    • 如果str1[m]/=str2[n]str1[m] \rlap{\,/}{=} str2[n],则L[m,n]=max( L[m,n1], L[m1,n] )L[m,n] = max ( ~ L[m,n - 1], ~L[m - 1, n] ~ )

    即如果不相等,保存前一个状态,以备相等时候的使用。并且这样某点的值必定不小于其左、上、左上的所有元素(好像这个结论并没有什么卵用)。

  • 博文介绍了一种二维数组的方法,这里贴一个滚动数组的(下标从1开始):

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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[210][2];
int main()
{
char s1[]=" ABCBDAB";
char s2[]=" BDCABA";
int len1=strlen(s1),len2=strlen(s2);
int maxn=0;
memset(dp,0,sizeof(dp));
for(int i=1,sta=0;i<len1;i++,sta=!sta)
{
for(int j=1;j<len2;j++)//注意变量初值
{
if(s1[i]==s2[j])
dp[j][sta]=dp[j-1][!sta]+1;
else
dp[j][sta]=max(dp[j-1][sta],dp[j][!sta]);//保留上方和左方的状态
printf("%d ",dp[j][sta]);
maxn=max(maxn,dp[j][sta]);
}
putchar('\n');
}
printf("%d\n",maxn);
return 0;
}

最长公共上升子串 O(n^2)

  • 理解了最长上升字串,看懂图之后这个应该不难写。

  • 先贴非滚动数组的代码(下标从1开始):

    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
    31
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210][210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    for(int j=1;j<len2;j++)
    {
    if(a1[i]==a2[j])
    if(a1[i]>a1[i-1])
    dp[i][j]=dp[i-1][j-1]+1;
    else
    dp[i][j]=1;
    else
    dp[i][j]=0;
    maxn=max(maxn,dp[i][j]);
    printf("%d ",dp[i][j]);
    }
    putchar('\n');
    }
    printf("%d\n",maxn);
    return 0;
    }
  • 讲一下滚动数组优化思路:很容易看出可以优化为2×n的二维数组,因为dp数组只跟i,j,i1,j1i,j,i-1,j-1有关,但也可以滚动成一维数组,因为发现它优化成一维数组没有障碍。它与i1,j1i-1,j-1相关,那么我们可以让内层循环从右往左循环,就可以保留上(指dp[i1][j]dp[i-1][j])和左上(指dp[i1][j1]dp[i-1][j-1])的状态了。

  • 一维数组滚动代码(下标从1开始):

    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
    31
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    for(int j=len2-1;j>=1;j--)
    {
    if(a1[i]==a2[j])
    if(a1[i]>a1[i-1])
    dp[j]=dp[j-1]+1;
    else
    dp[j]=1;
    else
    dp[j]=0;
    maxn=max(maxn,dp[j]);
    printf("%d ",dp[j]);
    }
    putchar('\n');
    }
    printf("%d\n",maxn);
    return 0;
    }

最长公共上升子序列 O(n^2)

  • 这个又提升了难度。

  • 贴个滚动数组的代码(下标从1开始):

    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
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    int m=0;
    for(int j=1;j<len2;j++)
    {
    if(a1[i]>a2[j])
    m=max(m,dp[j]);
    else if(a1[i]==a2[j])
    dp[j]=m+1;
    }
    }
    for(int j=0;j<len2;j++)
    maxn=max(maxn,dp[i]);
    printf("%d\n",maxn);
    system("pause");
    return 0;
    }
  • 看起来似乎很难以理解。这里有两种状态,一个是公共,一个是上升。其实它是将状态转移分离了,考虑这种情况:假设i=3,相应值是6,我们假定DP在运行到i=3之前都能正常工作,那么我从0到len2对序列2扫一遍,之前肯定有dp[1]=1,dp[4]=2(dp[j]表示以a2[j]结尾的最长公共子序列长度)。于是我在扫的过程中找到了a1[3]>a2[1],m存上1,又找到a1[3]>a2[4],m存上2,等到a1[3]==a2[5]的时候,我再开始转移,从dp[4]转移到dp[5],dp[5]变成了3。

  • 也就是说,只要dp[j]不为0,那a1[i]>a2[j]就保证了a1[i]>a1[k],其中a1[k]==a2[j],就保证了上升,a1[i]==a2[j]就保证了公共,dp状态的保存转移就保证了子序列。

  • 于是我想出一道变式,有兴趣的可以推一下:

变式:最长公共连续上升子序列



题目要求

  • 给出两个整数序列,求出其公共的连续上升数字的子序列的长度。

    {1,4,2,0,3,9,4,5}\lbrace 1,4,2,0,3,9,4,5 \rbrace{0,2,9,3,7,5,10}\lbrace 0,2,9,3,7,5,10 \rbrace的最长公共连续上升子序列为{2,3}\lbrace 2,3 \rbrace长度。


解题思路

  • 这道题仍然有两个状态,一个是公共,一个是连续上升,特性是子序列。其实你只要会了最长公共上升子序列,这道题就很容易推出来了。

  • 贴个滚动数组代码(下标从1开始):

    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
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,4,2,0,3,9,4,5};
    int a2[]={-1,0,2,9,3,7,5,10};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    int m=0;
    for(int j=1;j<len2;j++)
    {
    if(a1[i]==a2[j]+1)
    m=max(m,dp[j]);
    else if(a1[i]==a2[j])
    dp[j]=m+1;
    }

    }
    for(int j=0;j<len2;j++)
    maxn=max(maxn,dp[j]);//不要在外层循环滚动求最大值
    printf("%d\n",maxn);
    system("pause");
    return 0;
    }

最大子段和

算法1:分治策略递归求解 O(nlogn)

  • 用分治法递归,问题分解为:

    1. 求左半区域的最大子数组
    2. 求跨越中值的最大子数组
    3. 求右半区域的最大子数组

    由于当问题微分触底,1和3将被包含在2中,因此分解、解决、合并的步骤中,合并时只需要求2即可。

  • 算法导论4.1股票买卖:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
【问题】
算法导论4.1股票买卖:给出一个数组显示某公司17天每天股票的价格,假设你可以在任意一天结束时买入或卖出股票(只能进行一组买入及卖出),求最大收益及买卖日期。要求时间复杂度为o(n²)。

int A[17]={100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};

分治法复杂度O(nlogn)
*/
#include<stdio.h>
#define INF 0x3F3F3F3F
typedef struct {
int left;
int right;
int sum;
}structRet;

structRet FindMaxCrossingSubarray(int *Array, int left, int middle, int right)
{
int sum = 0,leftsum=-INF,rightsum=-INF,maxleft,maxright;
for (int i = middle; i >= left; i--)
{
sum += Array[i];
if (sum > leftsum)
{
leftsum = sum;
maxleft = i;
}
}
sum = 0;
for (int i = middle+1; i<= right; i++)
{
sum += Array[i];
if (sum > rightsum)
{
rightsum = sum;
maxright = i;
}
}
return structRet{ maxleft, maxright, leftsum + rightsum };
}
structRet FindMaxSubarray(int *Array, int left, int right)
{
if (left >= right)
return structRet{ left,right,Array[left] };
int middle = (left + right) / 2;
structRet ret1, ret2, ret3;
ret1=FindMaxSubarray(Array, left, middle);
ret2=FindMaxSubarray(Array, middle+1, right);
ret3=FindMaxCrossingSubarray(Array, left, middle, right);
if (ret1.sum >= ret2.sum)
{
if (ret1.sum >= ret3.sum)
return ret1;
else
return ret3;
}
else if (ret2.sum >= ret3.sum)
return ret2;
else
return ret3;

}

int main(void)
{
int _A[17] = { 100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97 };
int A[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
int B[6] = { -3,-5,-1,-7,-2,-8 };
structRet ret=FindMaxSubarray(B, 0, 5);
return 0;
}

算法2:动态规划求解 O(n)

  • 问题转化为找出最大子数组。用动态规划,假设尾部添加新的元素,则最大子数组将在不包含新元素的最大子数组和包含新元素的最大子数组中产生,其中包含新元素的最大子数组的状态转移方程为

    dp[i]=max(dp[i1]+a[i],a[i])dp[i]=max(dp[i-1]+a[i],a[i])

  • 编程之美给出了及其优美的线性解法:

1
2
3
4
5
6
7
8
9
10
11
int dpFindMaxSubarray(int *A, int n)    //动态规划 
{
int nAll = A[0]; //当前最大子段的和
int nEnd = 0; //以A[i]结尾的子数组最大和
for (int i = 0; i < n; i++)
{
nEnd = max(A[i], nEnd + A[i]); //求以A[i]结尾的和最大的子数组
nAll = max(nAll, nEnd); //当前和最大子段要么是以A[i]结尾,要么和A[i]无关
}
return nAll;
}

最大M子段和 O(n^2)

  • 简直是本专题完美的究极奥义啊,它帮我进一步完善了我蒟蒻的DP脑残思想,动态规划是指,通过一个正确的动态转移方程求得解,不管dp数组是一维还是二维还是三维的,只要在方程里ijk是变的,那就没错了。

    经典例题: A - Max Sum Plus Plus HDU - 1024

  • 看了题你大概就知道最大M子段和是啥意思了。

  • 动态转移方程:

dp[i][j]=max(dp[i][j-1]+a[i],max(dp[0][j-1]dp[i-1][j-1])+a[i])\text{dp[i][j]=max(dp[i][j-1]+a[i],max(dp[0][j-1]} \sim \text{dp[i-1][j-1])+a[i])}

  • 其中ii是段数,jj是以jj为结尾(必须包含jj)。那么开始考虑分成ii段的时候,以jj结尾的话,要么a[j]a[j]被包含在最后一段里(即dp[i][j1]+a[i]\color{grey}{dp[i][j-1]+a[i]}),要么jj独自成段。如果jj独自成段,就从i1i-1段的状态里面找个最大值转移过来(即max{dp[i1][i1j1]}+a[i]\color{grey}{max\{dp[i-1][i-1 \sim j-1]\}+a[i]})。如果直接做是O(n3)O(n^3)的,但找最大值的这里可以进行滚动,将时间复杂度压为O(n2)O(n^2)

  • 在将算法转化为代码的过程中,我感觉最为困难的是将最大值转移的那一块,我找到了一个将lmax开成lmax[1000010][2]\text{lmax}[1000010][2]的滚动数组的方法,但总认为不好,于是在这部分借鉴了一下网上的做法,我觉得十分巧妙。

  • 贴上代码(有很多坑):

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
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int a[1000010];
int dp[1000010];
int m,n;
int lmax[1000010]; //lmax[n]是指上一轮里dp[1]~dp[n]里面的最大值
int solve()
{
fill(dp,dp+n+1,0);
fill(lmax,lmax+n+1,0);
int tmp=0;//0段的结果是0
m=min(m,n);//段数m不能大于n
for(int i=1;i<=m;i++)//分为i段
{
tmp=-INF;
for(int j=i;j<=n;j++)//这里必须注意j的初值,因为如果分i段的话,是不可能以a[1]~a[i-1]结尾的
{
dp[j]=max(dp[j-1],lmax[j-1])+a[j];
lmax[j-1]=tmp;//lmax维护上一轮的以i-1~j-1结尾的dp最大值
tmp=max(tmp,dp[j]);//巧妙借助一个tmp变量,延时赋值,使得本轮的dp值不会覆盖马上要使用的上一轮的lmax。
//滚动数组时,使用过的转移才能更新,未使用过的转移不能更新。这里lmax[j-1]使用过才能更新。
}
}
return tmp;
}
int main(void)
{
while(scanf("%d %d",&m,&n)==2)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d\n",solve());
}
return 0;
}

不烧脑滚动:

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
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int a[1000010];
int dp[1000010];
int m,n;
int lmax[1000010][2];
int solve()
{
fill(dp,dp+n+1,0);
fill(lmax,lmax+n+1,0);
int tmp=0;//0段的结果是0
m=min(m,n);//段数m不能大于n
for(int i=1;i<=m;i++)//分为i段
{
tmp=-INF;//lmax维护的是i-1~j-1的左区间最大值,所以每次都要刷新
for(int j=i;j<=n;j++)//这里必须注意j的初值,因为如果分i段的话,是不可能以a[1]~a[i-1]结尾的
{
dp[j]=max(dp[j-1],lmax[j-1][i&1])+a[j];
tmp=max(tmp,dp[j]);
lmax[j][!(i&1)]=tmp;
}
}
return tmp;
}
int main(void)
{
while(scanf("%d %d",&m,&n)==2)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d\n",solve());
}
return 0;
}

钱币兑换问题

http://acm.hdu.edu.cn/showproblem.php?pid=1284

在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

这道题可用dfs、公式、dp解决。

找规律与公式

先给出公式的解法(推出一个一行的公式估计也是可以的,但没必要):

找规律可知,总数等于3分硬币取0,1,2...i0,1,2...i个的情况下2分硬币取0,1,2...j0,1,2...j个的情况数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

int n;

int main(){
while(~scanf("%d",&n)){
ll cnt=0;
for(int i=0;i<=n;i+=3){
ll ret=n-i;
cnt+=ret/2+1;
}
printf("%d\n",cnt);
}
return 0;
}

上述写法是因为只有1、2、3的硬币,如果有0~k个硬币,用dfs改造一下可解。

DP角度

在DP角度来看,这道题是个组合数问题,如果dp变量只有一个,那么是一个排列数。

为了要实现组合数,需要另加一个变量来解决,这个变量的转移需要规定一个顺序,很容易想到可以从小到大先用小的硬币再用大的硬币;或者从大到小,先用大的硬币,再用小的硬币。我认为后者更简单。

整数拆分问题

凭经验可知这道题可由整数拆分问题解决。

https://blog.csdn.net/weixin_40163242/article/details/87532355

整数拆分问题引用了两个变量, 一个是整数n,一个是使用不超过m的整数对n进行拆分。

dp[n][m]dp[n][m]表示使用不超过m的整数对n进行拆分的分法数目。

本题m取3即可。

整数拆分问题:

需要注意的是初始点该怎么赋值。

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
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

int n;

ll dp[40000][3];

int main(){
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
for(int i=0;i<=3;i++){
dp[1][i]=dp[0][i]=1;
}
for(int i=0;i<=n;i++){
dp[i][1]=dp[i][0]=1;
}
for(int i=2;i<=n;i++){
for(int j=2;j<=3;j++){
if(i<j){
dp[i][j]=dp[i][i];
}else if(i==j){
dp[i][j]=dp[i][j-1]+1;
}else{
dp[i][j]=dp[i-j][j]+dp[i][j-1];
}
}
}
printf("%lld\n",dp[n][3]);
}
return 0;
}

另一种方法

喵老板想了另一种转移的方法:

dp[i][j]=k=ik=j,k0dp[k][j1],i>=1dp[i][j]=1,i=1 or j=1\begin {aligned} dp[i][j]&=\sum_{k=i}^{k-=j,k\geqslant 0} dp[k][j-1]&,i>=1\\ dp[i][j]&=1&,i=1~or~j=1 \end {aligned}

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
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

int n;

ll dp[40000][3];

int main(){
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][1]=dp[i][0]=1;
}
for(int i=1;i<=3;i++){
dp[0][i]=dp[1][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=2;j<=3;j++){
for(int k=i;k>=0;k-=j){
dp[i][j] += dp[k][j-1];
}
}
}
printf("%lld\n",dp[n][3]);
}
return 0;
}

这个是O(n3)O(n^3)的,会TLE。

画图可知dp[i][j]dp[i][j]是从上一层的dp[i3,i6,...,ik][j1]dp[i-3,i-6,...,i-k][j-1]转移过来的,而dp[i+3][j1]dp[i+3][j-1]是从上一层的dp[i,i3,i6,...,ik][j1]dp[i,i-3,i-6,...,i-k][j-1]转移过来的,可以看到是可滚动的,改表达式为:

dp[i][j]=dp[ij][j]+dp[i][j1],i>=1dp[i][j]=1,i=1 or j=1\begin {aligned} dp[i][j]&=dp[i-j][j]+dp[i][j-1]&,i>=1\\ dp[i][j]&=1&,i=1~or~j=1 \end {aligned}

可以看到刚好转换为了整数拆分的dp转移式。

代码:

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
31
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

int n;

ll dp[40000][3];

int main(){
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i][1]=dp[i][0]=1;
}
for(int i=1;i<=3;i++){
dp[0][i]=dp[1][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=2;j<=3;j++){
if(i-j<0){
dp[i][j]=dp[i][i];
continue;
}
dp[i][j] = dp[i-j][j] + dp[i][j-1];
}
}
printf("%lld\n",dp[n][3]);
}
return 0;
}

DP总结:针对一个DP问题该如何思考

在做dp问题的时候,应该从哪些方面进行思考?

这几天做了一些dp题,找到了一些共性,希望能够总结出来,理一个清晰思路。

如何确定dp候选变量

比方说最大M子段和,为什么有两个变量,段数、以j结尾,组成dp[i][j]dp[i][j]

再比方说打怪兽的题,为什么有三个变量,轮数、未来攻击次数、未来攻击次数所在轮数下标和。

由于dp是最优子结构的问题,首先我们可能会想到,目标是M子段,在问题规模缩小的情况下,子段的数量可能是一个变量。

考虑问题规模作为变量

因此首先考虑的问题是,问题规模是一个变量

回顾一下动态规划的性质:

  1. 动态规划要保证每个子问题相互重叠
  2. 动态规划分解后的问题依然是相同结构的规模更小的子问题,且具有最优子结构性质
  3. 动态规划需要无后效性

对于最优子结构,我们必须辩证去看。

我们需要注意,问题规模作为单独一个变量时,问题规模=n时并不代表问题的解决,还要配合其他变量的值才能表示问题的解决。

最优子结构是指问题的最优解包含子问题的最优解。但如果问题规模不是唯一的变量,那么我们dp[i][j][k]..[y][z]dp[i][j][k]..[y][z](其中ii代表问题规模)代表的问题就很有可能不是原问题了,此时dp变量的一个可能取值的组合极有可能并不代表原问题的最优解。

举个实际例子,比方说打怪兽的题,原问题的最优解的意义下,问题规模=n时候,第n轮必须选择攻击,该原问题才能达到最优解,但实际上,由于问题规模不是唯一的变量, dp变量的一个可能取值的组合并不代表原问题的最优解,只有当问题规模即轮数=n,且未来攻击次数=0,且未来攻击次数所在轮数下标和=0时才是问题规模=n时原问题的最优解。

当然,当问题规模是唯一的变量时,dp[m]dp[m]必然代表问题规模为m的子问题的最优解。

那么,什么是问题规模?

候选的问题规模有很多个,比如说在最大M子段和问题中,问题规模可以为:

  1. 子段数量
  2. 考虑的数组长度(即以jj为最后一段的尾元素)

打怪兽问题中,问题规模可以为:

  1. 轮数

划区灌溉问题中,问题规模可以为:

  1. 考虑的数组长度(以jj为最后一个喷灌器的右端点)。或分解为两个变量:1,数组长度。2,最后一个喷灌器的右端点。要视具体情况考虑需不需要这么分。
  2. 已跨过的奶牛数

问题规模不一定都要作为变量,可能是全部,可能是一部分。

在思考如何转移时引入变量

另外,我们可以在思考如何转移时引入变量。

考虑转移时目标值受到什么变量的影响?

目标值是指dp[i][j][k]..[y][z]dp[i][j][k]..[y][z]的值,其中i,j,k,...,y,zi,j,k,...,y,z都是dp变量。

举例,在打怪兽问题中,目标值——最终伤害值,受到什么变量的影响?

很显然,在第ii轮时,我选择攻击——造成A+aiA+a_i的伤害;我选择增加攻击力——以后每次攻击都会增加cic_i的伤害;我选择增加攻击力增量——以后每一轮都会多增加bib_i点攻击力,体现在第jj轮进行攻击的话会贡献bi(ji)b_i*(j-i)的伤害;

总结一下,目标值受到未来攻击次数,以及攻击的轮数下标的影响。

未来攻击次数可以作为一个变量,但攻击的轮数下标是多个值,不能作为一个变量。这时思考一下,如果我未来攻击3次,在第j,k,l轮进行攻击,那么我第ii轮增加攻击增量会贡献bi(ji+ki+li)=bi(j+k+l3i)b_i*(j-i+k-i+l-i)=b_i*(j+k+l-3*i)点伤害。因此我只需要记录未来攻击轮数的下标和即可。

因此三个变量为:

  1. 轮数
  2. 未来攻击次数
  3. 未来进行攻击的轮数的下标和

如何进行转移,以及确定dp变量

如何转移会影响到dp变量的选取。

比方说,划区灌溉问题中,我们可以使用两种问题规模:

  1. 考虑的数组长度(以jj为最后一个喷灌器的右端点)
  2. 已跨过的奶牛数

如果我们考虑数组长度(以jj为最后一个喷灌器的右端点)作为一个变量,那么我们需要考虑数组是否开得下。

数组一般最多可开1e7的长度,具体要看内存限制。

如内存限制65536 kB,则最多可开一个65536*1024/4=‭16,777,216‬长度的int数组。

题目中给出1 <= L <= 1,000,000,空间复杂度可行。

时间复杂度上,1s的话最多可计算1e8次。

时间复杂度上,1e6的数据量下转移算法复杂度最多是O(nlogn)O(nlogn)的。

那么很容易想到固定右端点,枚举左端点进行转移,再看到是一个滑动窗口,即可以使用单调队列处理。

那么就无需考虑另一个候选变量——已跨过的奶牛数了。

再举个例子,在最大M子段和问题中,问题规模可为:

  1. 子段数量
  2. 考虑的数组长度(即以jj为最后一段的尾元素)

不考虑子段数量作为问题规模的话,则默认子段数量为M吗?在数组元素少于M时,这个想法是不切实际的。所以子段数量应该要考虑。

再看考虑的数组长度(即以jj为最后一段的尾元素),以jj结尾的话,要么jj独立成段,dp[i][j]dp[i][j]dp[i1][i1,i2,...,j1]dp[i-1][i-1,i-2,...,j-1]转移过来;要么jj合并到最后一段,从dp[i][j1]dp[i][j-1]转移过来;我们取两种转移方式的最优。

对于从dp[i1][i1,i2,...,j1]dp[i-1][i-1,i-2,...,j-1]转移来说,可以维护一个最大值数组,保证O(1)转移。

考虑非法转移点

比方说划区灌溉的题,奶牛所在的区域不能作为喷灌器的左端点的落点,因此奶牛所在的区域是非法转移点,我们不能从这些点转移过来。

再比如说打怪兽的题,当前轮数ii、未来攻击次数jj、未来攻击次数所在轮数下标和kk之间存在关系:k>ijk>i*j,因此下标不满足这个关系的都是非法转移点。

考虑初始点

不仅要给非法转移点赋值一个非法dp值,或使用单独的数组标记,一定要给初始点赋值一个初始值。

如划区灌溉的题,初始点是dp[0]=0dp[0]=0

如打怪兽的题,当i=0i=0时,无论jjkk取任意值,dp[i][j][k]=0dp[i][j][k]=0

文章目录
  1. 1. 最长上升子序列
    1. 1.1. 性质
    2. 1.2. 二分复杂度优化 O(nlogn)
    3. 1.3. 例题1:拦截导弹
    4. 1.4. 例题2:最少拦截系统
    5. 1.5. 例题3:Wooden Sticks
  2. 2. 最长公共子串(dp) O(n^2)
  3. 3. 最长公共子序列 O(n^2)
  4. 4. 最长公共上升子串 O(n^2)
  5. 5. 最长公共上升子序列 O(n^2)
    1. 5.1. 变式:最长公共连续上升子序列
      1. 5.1.1. 题目要求
      2. 5.1.2. 解题思路
  6. 6. 最大子段和
    1. 6.1. 算法1:分治策略递归求解 O(nlogn)
    2. 6.2. 算法2:动态规划求解 O(n)
  7. 7. 最大M子段和 O(n^2)
  8. 8. 钱币兑换问题
    1. 8.1. 找规律与公式
    2. 8.2. DP角度
      1. 8.2.1. 整数拆分问题
      2. 8.2.2. 另一种方法
  9. 9. DP总结:针对一个DP问题该如何思考
    1. 9.1. 如何确定dp候选变量
      1. 9.1.1. 考虑问题规模作为变量
      2. 9.1.2. 在思考如何转移时引入变量
    2. 9.2. 如何进行转移,以及确定dp变量
    3. 9.3. 考虑非法转移点
    4. 9.4. 考虑初始点