今天学习了两个基础DP，分享一下。

一、最大子段和

求一段序列中的一段子序列，使得这段子序列的和最大:

①普通做法:

我们完全可以 枚举法 来做 ，即二层for循环，第一层枚举起点，二层枚举长度，用一个sum来记录当前的和。枚举完之后，最大子段和即为sum。

时间复杂度 O(N^2)

②DP做法：

 

1)：我们用一个数组dp[i]记录一下，以i结尾序列中子序列可产生的最大和。eg: {1,2,3} 前三个数会产生 {1,2,3}，{1,3},{2,3},还{3}。

 

2)：这里注意：以i结尾说明 i 一定为该序列的结尾。

 

3)：所以我们对应第i个数来说，有以下两种选择：

第一种情况：第i个数与i-1个数构成一个子段，即与以（i-1）结尾的子段融合。

第二种情况：第i个数单独 成为 一个子段 。

所以状态转移方程：dp[i]=max(dp[i-1]+num[i],num[i]);

 

4)：接下来我们只需要记录过程中产生的最大值就好了。

分析一下DP的最优性:以序列S={1,-2,3,-3,5}为例：（其实就等于画表格，因为一维就可以直接列了）

按照DP的原理：1.第一个数可以自己一个子段或者与其之前的构成一个子段 dp[i-1]=0，所以sum=1。

 

2.第二个数同样可以与之前组成一个序列 {1,-2}=-1，或者自己单独序列=-2，所以sum=-1

 

3.第三个数同样 要么-1与3，要么3单独，所以sum=3。

 

4.同理，第四个数0与-3 选择 0 ，sum=0,第五个数 5与5 选择5 sum=5 

 

5.记录过程中最大值的话，maxl=5，即{3,-3,5}构成的子段。

从过程中我们可以看出来，对于任何一个i，我们可以根据 i-1的最优性，再对i的情况进行考虑，选择最优。使得i成为最优，从而还可以推出i+1最优。

代码：

ll n,m,k;
ll x,y;
ll num[maxn];
ll dp[maxn];
int main()
{
    while(~scanf("%lld",&n)&&n)
    {
        for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
        ll maxl=-INF;
        for(int i=1;i<=n;i++)
        {
            dp[i]=max(dp[i-1]+num[i],num[i]);
            maxl=max(maxl,dp[i]);
        }
        printf("%lld\n",maxl);
    }
    return 0;
}

 

思考：如何输出组成最大字段和的数？

其实不难，我们只需要把过程倒着推回去即可。根据我们上述的推导过程，如果在dp[i]处最大子段和最大，那么这个子段和是以i结尾的，所以这个子段和有两种可能，第一种与num[i-1]相连 第二种自己相连。所以我们只需要判断 i 处是不是由前面i-1推导而来即可，如果是由i-1推到而来，那么它一定满足 dp[i-1]=dp[i]-num[i]。否则他则是自己单独成为子段。

所以代码如下：

ll num[maxn];
ll dp[maxn];
bool vis[maxn];
void check()
{
    ll minl=1;//如果序列元素都属于子段的话，起始位置应该从1开始
    for(int i=k;i>=1;i--)
    {
        if(dp[i]-num[i]!=dp[i-1])
        {
            minl=i;
            break;
        }
    }
    for(int i=minl;i<=k;i++)
        printf("%lld ",num[i]);
}
int main()
{
    while(~scanf("%lld",&n)&&n)
    {
        for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
        ll maxl=-INF;
        for(int i=1;i<=n;i++)
        {
            dp[i]=max(dp[i-1]+num[i],num[i]);
            if(maxl<dp[i])
            {
                k=i;
                maxl=dp[i];
            }
        }
        check();
    }
    return 0;
}

二、最大m子段和

对于一段序列 S来说，我们可以从S中选出 互不相交的m个子段，使得这m个子段，使得m个子段 和最大，m的大小不限。

①这样的话基本做法就有点行不通了。时间复杂度与难想程度兼具。

②用一下DP的思路：

 

1)：首先我们应该想，如何用一个数组记录，这里我们可以参考一下01背包的思路，我们可以 将 前i个数字，分成j段的最优值记录，最后我们只需要遍历 dp[t][m] (m=<t<=n)

 

2)：所以，思路即为：用一个dp[i][j]数组记录，前i个数字分成j段所能产生的最大j子段和，前提必须以i结尾。

 

3)：这个前提的要求，提供了第i个数字的可能情况:

第一：第i个数字单独成为一段，与之前的 j-1段 组合。

第二：第i个数字与第i-1个数字融合成为第j段。

 

4)：所以状态转移方程即为：dp[i][j]=max(dp[i-1][j],max(dp[t][j-1])(j-1=<t<i))+num[i]。

关于第二个dp[t][j-1]的解释：(首先盗用一波学长的图)

比如说我们 对 dp[6][3]考虑时，我们需要看一下 分成 2段时的最优解，那么就是 24。

如果还不懂最大m子段和的话，这张图 加上 自己 用集合 画一画 是拯救你的最后一种方法！

 

5)：我们现在已经 把 dp的整体思路 弄懂了，剩下的问题就是如何优化：

其中有这么几个优化点：

第一：我们考虑 分成j段时，应该从 第 j 个数开始 判断 ，因为 比如分成五段 i=4根本不可能。

第二：我们在做比较时，只比较了 从 j-1到i-1 中 分成j-1段时的最大值，其余的用不到,比如说上图中的 dp[3][6] 我们只需要 计算dp[2][2]到dp[2][5]之间的最大值。所以从i枚举到 (n-m+i)即可，不懂的话看下面的图：

黑色与白色的部分使我们不需要求的，我们要求分成m段，最少需要知道上一层的最后一个数，上一层最后一个数就是 n-m+i个数，所以就可以这么枚举。

第三：空间复杂度的优化，因为我们推到分成j段只需要 考虑 分成j-1段的情况，所以我们不用开 m*n的数组，只需要开 2*n的数组即可。

6)：具体细节还是在代码里说比较好:

#define PI 3.1415926535
#include <set>
#define E 2.718281828459
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e9;

const int maxn=1e6+5;

const ll mod=10000000007;
const double eps=1e-10;
ll n,m,k;
ll x,y;
ll num[maxn];
ll dp[2][maxn];
int main()
{
    while(~scanf("%lld%lld",&m,&n))
    {
        for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
        for(int i=0;i<=n;i++) dp[0][i]=dp[1][i]=0;
        for(int i=1,k=1;i<=m;i++,k^=1) //遍历分为每一段
        {
            ll maxl=-INF; dp[k][i-1]=-INF;//i=j时，j只有一种选择就是与j-1段的最优解进行合并，因为在i=j之前他无法分成j段
            for(int j=i;j<=n-m+i;j++)
            {
                maxl=max(maxl,dp[k^1][j-1]);//记录上一个序列到j-1位置时的最大值。
                dp[k][j]=max(dp[k][j-1],maxl)+num[j];//状态转移
            }
        }
        ll ans=-INF;
        for(int i=m;i<=n;i++)//从上图我们也可以看出出现值是从i=m开始出现的
            ans=max(ans,dp[m&1][i]);//判断一下m为奇数还是偶数，m为偶数的话，最终结果应该在dp[0]内，否则dp[1]内，然后又刚好与与运算相同
        printf("%lld\n",ans);
    }
    return 0;
}

完结，当然动态规划的优化确实是太有用，继续加油，戒骄戒躁！