线性DP图文实例讲解

线性DP，所谓线性DP，就是指我们的递归方程有一个明显的线性关系的，有可能是一维线性的，也可能是二维线性的。

例题一：大盗阿福

题目：阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 NN 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式

输入的第一行是一个整数 T (T≤50) ，表示一共有 TT 组数据。

接下来的每组数据，第一行是一个整数 N (1≤N≤100000)，表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000。

输出格式

对于每组数据，输出一行。

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

提示

对于第一组样例，阿福选择第 2家店铺行窃，获得的现金数量为 8。对于第二组样例，阿福选择第 1 和 4 家店铺行窃，获得的现金数量为 10 + 14 = 24。

样例输入

2
3
1 8 2
4
10 7 6 14

样例输出

8

24

解题方法一

（1）状态表示：

f[i]表示偷前i家店铺能获取的最大值。

（2）状态转移：

状态转移可以用带权的有向图表示，点表示状态，权表示转移的价值增量。

转移的情况：

1. 不选第 i 家店铺，那么就可以选择第 i-1家店铺，所以f[i]=f[i-1]

2. 选第 i 家店铺，那么就不能选择第 i-1 家店铺，只能选择第 i-2 家店铺，因为会选择第 i 家店铺，所以f[i]=f[i-2]+w[i]

（3）边界情况：

根据题意即可知边界为：

1. 第0家店铺：f[0]=0

2. 第1家店铺：f[1]=w[1]

（4）代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int f[N];
int w[N];
int main ()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for(int i=1;i<=m;i++)
        cin>>w[i];
        //dp
        f[1]=w[1];//边界条件
        for(int i=2;i<=m;i++)
            f[i]=max(f[i-1],f[i-2]+w[i]);

        cout<<f[m]<<endl;
    }
    return 0;
}

解题方法二

（1）状态表示：

f[i][0] 表示不偷第 i 家店铺能获得的最大值

f[i][1] 表示偷第 i 家店铺能获得的最大值

（2）状态转移：

转移递推式：

不偷：f[i][0]=max( f[i-1][0] , f[i-1][1])

偷：f[i][1]=f[i-1][0] + w[i]

（3）边界情况：

根据题意可知边界为：

1. 不偷第 1 家店铺：f[1][0]=0

2. 偷第 1 家店铺 f[i][1]=w[1]

（4）代码如下：

//  时间：2022.09.07 18点09分
//  算法：线性DP
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N];
int w[N];
int main ()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for(int i=1;i<=m;i++)
            cin>>w[i];
        //dp
        f[1][0]=0,f[1][1]=w[1];
        for(int i=2;i<=m;i++){
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][0]+w[i];
        }
        cout<<max(f[m][0],f[m][1])<<endl;
    }
    return 0;
}

例题二：股票买卖

原题：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析：

（1）状态表示：

1. f[i][0] 表示第 i 天手中无票时获取的最大利润

2. f[i][1] 表示第 i 天手中有票时获得最大利润

（2）状态转移：

状态转移递推式：

1. 无票：f[i][0]=max(f[i-1][0],f[i-1][1] + w[i])

2. 有票：f[i][1]=max(f[i-1][1], f[i-1][0] - w[i])

（3）边界情况：

1. 第1天无票：f[1][0]=0

2. 第1天有票：f[1][1]=w[1]

（4）代码如下：

//  时间：2022.09.07 19点56分
//  算法：线性DP
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N];
int w[N];
int main ()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
        
        f[1][0]=0,f[1][1]= -w[1];
        //dp
        for(int i=2;i<=n;i++){
            f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);
            f[i][1]=max(f[i-1][1],f[i-1][0]-w[i]);
        }

        cout<<f[n][0]<<endl;
    return 0;
}

例题三：数字三角形

题目：给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

输入格式

第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500,

−10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

分析：

代码如下：

// 算法：动态规划之线性DP
// 时间：2022.07.13 15点45分
#include<iostream>
#include<algorithm>
using namespace std;

const int N=510;
int n,INF=1e9;
int a[N][N],f[N][N];
int main ()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];

    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)
//注意此时初始化需要多初始化一位，因为算边界时会算右上角的最大值，所以把最上角初始化为负无穷    
            f[i][j]=-INF;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        
    //遍历最后一行的最大值
    int res=-INF;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    
    cout<<res<<endl;
    return 0;
}