动态规划模型

动态规划1中已经介绍了一些动态规划的一些基本内容，现在我们从三道题来看一下动态规划的模型。

1.最大字段和

给定一个由数字组成的序列，其中连续的一段子序列称为一个子段，子段中的所有数只和称为子段和，这里只考虑非空子段，即至少包含一个元素的子序列，那么现在需要你求出有一个序列中的最大子段和。

当然我们可以用o(n^3）的暴力算法来解决这道题，也可以用前缀和优化成o(n^2)的算法来解决，但是如果这一段子序列太长，那么肯定会超时的。这时候我们就需要用动态规划来解决这道题了。

首先我们来描述这道题，求最大子段和的阶段是末端点为n的子段和，而他的状态就是末端点为n的最大子段和,决策就是是否把当前最大子段和状态值设为0(如果dp[i]此时最大子段和是一个负数，那么减掉前i段的前缀和对于这个点肯定肯定更优，并且这个子段要尽量往前延伸），那么这时候我们就可以推出他的状态转移方程了，需要注意的一点就是需要在进行扫描的时候需要每一次都把dp[i]与ans进行比较(因为你不能肯定最后dp[n]肯定是这题的答案），还有当dp[i]<0时要进行决策，把当前最大子段和状态值设为0(舍去前i段的前缀和），以供后面的最大子段和的计算。还有一点要注意的就是需要特判一下该序列全为负数时。

我们来模拟一下这个过程：

下面就是代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int N=10000;
const int inf=100000000;
int dp[N],a[N];
int main()
{
    int n,sum=0;
    cin>>n;
    int ans=-inf;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans=max(ans,a[i]);
    }
    if(ans<=0)cout<<ans<<endl;
    else
    {
        for(int i=1;i<=n;i++)
        {
            dp[i]=dp[i-1]+a[i];
            ans=max(dp[i],ans);
            if(dp[i]<0)
                dp[i]=0;
        }
        cout<<ans<<endl;
    }
    return 0;
}

2.下面我们再来看一道题：

最长上升子序列是动态规划的一个经典应用

在原序列取任意多项，不改变他们在原来数列的先后次序，得到的序列称为原序列的子序列。最长上升子序列，就是给定序列的一个最长的、数值从低到高排列的子序列，最长上升子序列不一定是唯一的。比如，序列2，1，5，3，6，4，6，3的最长上升子序列为1，3，4，6和2，3，4，6，长度均为4。

所以我们需要描述一下这道题，很显然这题用一维就可以去描述了，而这题的阶段就是以第i项作为结尾端点的上升子序列（即dp[i]），而这题的状态就是第i个位置的最长上升子序列的长度，决策的话就是第i个位置是否加入要计算的最长上升子序列(a[j]<a[i],j<i这样的情况才能加入)，所以我们就可以推出来他的转移方程：，其实这就是一个带有最优子结构的递推转移方程，如果满足加入最长上升子序列的条件后我们并不一定非得必须加入（因为之前还有可能有以他为结尾的更长的上升子序列）。需要注意的一点是我们需要用两层for循环来找出他的最长上升子序列长度(因为最长上升子序列不是唯一的，所以每一个起点都要去试一下）。         

这是递推打表之后得到的模拟表：

下面则是最长上升子序列的代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N=10000;
const int inf=100000000;
int ans=0,a[N],dp[N];
int main()
{
    int n;
    cin>>n;
    ans=-inf;
    for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j<i&&a[j]<a[i])
            dp[i]=max(dp[i],dp[j]+1);
            ans=max(dp[i],ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}

3.下面我们再来看一道题：

LCS(最长公共子序列)

最长公共子序列：给定两个序列S1和S2，求两者公共子序列S3的最长的长度。

我们很显然可以发现这个问题依然可以按照序列的长度来划分状态。这里需要注意的是要求的是最长公共子序列，即可以不连续，只要是公共序列就好。

我们可以用二维来去描述这个问题，阶段就是S1以i为末端的公共子序列的长度和S2以j为末端的公共子序列的长度，状态就是S1以i为末端的最长公共子序列的长度和S2以j为末端的公最长共子序列的长度，决策就是最长公共子序列的长度是否加以（很显然，当S1的第i位和S2的第j位相同时我们的最长公共子序列长度肯定+1,如果不相同时我们可以把s1的第i-1位和s2的j位的最长上升子序列长度以及s1的第i位和s2的j-1位的最长上升子序列长度这两个状态求最大值之后转移过来(这两个状态最大值已经计算出来了），就是如果不相同的话我们需要把比较位再缩进一下，但不要全部缩进，[s1]:3 4 2 [s2]:3 2 4,像这样单位缩进一下就能得到我们想要的结果了，也就是S[i][j]的状态是由S[i][j-1]的状态转移过来的，而S[i][j-1]的状态值我们之前已经计算过了，我们只是想要更新一下以供后面的计算，总体来说我们的决策就是不相同的时候把s[i-1][j]和s[i][j-1]的最大值转移过到s[i][j]，你可以想想我动态规划1里的那个蒜头君回家的那个例子，这里能到达s[i][j]的相邻两个状态只有s[i-1][j]和s[i][j-1]）那么我们就可以得到这个问题的转移方程了:S[i][j]=S[i-1][j-1]+1,a[i]==a[j];S[i][j]=max(S[i-1][j],S[i][j-1]),a[i]!=a[j];（一定要注意S[i][j]代表着s1的前i个字符和s2的前j个字符的最长公共子序列)有了状态转移方程之后，我们当然是从前往后去递推的。这里不用处理边界条件，因为dp[0][0]=0,初始值的话都是0，也没有什么需要特判的条件。

下面是递推打表之后的表：

下面是这题的代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N=10000;
const int inf=10000000;

int a[N],b[N],dp[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    int ans=-inf;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    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]);
            }
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}