線性DP，所謂線性DP，就是指我們的遞歸方程有一個(gè)明顯的線性關(guān)系的，有可能是一維線性的，也可能是二維線性的。

例題一：大盜阿福

題目：阿福是一名經(jīng)驗(yàn)豐富的大盜。趁著月黑風(fēng)高，阿福打算今晚洗劫一條街上的店鋪。

這條街上一共有 NN 家店鋪，每家店中都有一些現(xiàn)金。阿福事先調(diào)查得知，只有當(dāng)他同時(shí)洗劫了兩家相鄰的店鋪時(shí)，街上的報(bào)警系統(tǒng)才會(huì)啟動(dòng)，然后警察就會(huì)蜂擁而至。

作為一向謹(jǐn)慎作案的大盜，阿福不愿意冒著被警察追捕的風(fēng)險(xiǎn)行竊。他想知道，在不驚動(dòng)警察的情況下，他今晚最多可以得到多少現(xiàn)金？

輸入格式

輸入的第一行是一個(gè)整數(shù) T (T≤50) ，表示一共有 TT 組數(shù)據(jù)。

接下來的每組數(shù)據(jù)，第一行是一個(gè)整數(shù) N (1≤N≤100000)，表示一共有 N 家店鋪。

第二行是 N 個(gè)被空格分開的正整數(shù)，表示每一家店鋪中的現(xiàn)金數(shù)量。每家店鋪中的現(xiàn)金數(shù)量均不超過 1000。

輸出格式

對于每組數(shù)據(jù)，輸出一行。

該行包含一個(gè)整數(shù)，表示阿福在不驚動(dòng)警察的情況下可以得到的現(xiàn)金數(shù)量。

提示

對于第一組樣例，阿福選擇第 2家店鋪行竊，獲得的現(xiàn)金數(shù)量為 8。對于第二組樣例，阿福選擇第 1 和 4 家店鋪行竊，獲得的現(xiàn)金數(shù)量為 10 + 14 = 24。

樣例輸入

2
3
1 8 2
4
10 7 6 14

樣例輸出

8

24

解題方法一

（1）狀態(tài)表示：

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

（2）狀態(tài)轉(zhuǎn)移：

狀態(tài)轉(zhuǎn)移可以用帶權(quán)的有向圖表示，點(diǎn)表示狀態(tài)，權(quán)表示轉(zhuǎn)移的價(jià)值增量。

轉(zhuǎn)移的情況：

1. 不選第 i 家店鋪，那么就可以選擇第 i-1家店鋪，所以f[i]=f[i-1]

2. 選第 i 家店鋪，那么就不能選擇第 i-1 家店鋪，只能選擇第 i-2 家店鋪，因?yàn)闀?huì)選擇第 i 家店鋪，所以f[i]=f[i-2]+w[i]

（3）邊界情況：

根據(jù)題意即可知邊界為：

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）狀態(tài)表示：

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

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

（2）狀態(tài)轉(zhuǎn)移：

轉(zhuǎn)移遞推式：

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

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

（3）邊界情況：

根據(jù)題意可知邊界為：

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

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

（4）代碼如下：

//  時(shí)間：2022.09.07 18點(diǎn)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;
}

例題二：股票買賣

原題：

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

分析：

（1）狀態(tài)表示：

1. f[i][0] 表示第 i 天手中無票時(shí)獲取的最大利潤

2. f[i][1] 表示第 i 天手中有票時(shí)獲得最大利潤

（2）狀態(tài)轉(zhuǎn)移：

狀態(tài)轉(zhuǎn)移遞推式：

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）代碼如下：

//  時(shí)間：2022.09.07 19點(diǎn)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;
}

例題三：數(shù)字三角形

題目：給定一個(gè)如下圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇移動(dòng)至其左下方的結(jié)點(diǎn)或移動(dòng)至其右下方的結(jié)點(diǎn)，一直走到底層，要求找出一條路徑，使路徑上的數(shù)字的和最大。

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

輸入格式

第一行包含整數(shù) n，表示數(shù)字三角形的層數(shù)。

接下來 n 行，每行包含若干整數(shù)，其中第 i 行表示數(shù)字三角形第 i 層包含的整數(shù)。

輸出格式

輸出一個(gè)整數(shù)，表示最大的路徑數(shù)字和。

數(shù)據(jù)范圍

1≤n≤500,

?10000≤三角形中的整數(shù)≤10000

輸入樣例：

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

輸出樣例：

30

分析：

代碼如下：

// 算法：動(dòng)態(tài)規(guī)劃之線性DP
// 時(shí)間：2022.07.13 15點(diǎn)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++)
//注意此時(shí)初始化需要多初始化一位，因?yàn)樗氵吔鐣r(shí)會(huì)算右上角的最大值，所以把最上角初始化為負(fù)無窮    
            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;
}