高能預(yù)警：講了這么久動態(tài)規(guī)劃了，該上點有難度的題吧

目錄

題目：方格取數(shù)

?思路（解法一）：

?解法二：

---

題目：方格取數(shù)

? ? ? ??

?思路（解法一）：

如果只有兩個方向的話，動態(tài)規(guī)劃就很簡單了，因為很容易就能根據(jù)已確定點推出未確定點（因為每個未知點都可以由上方和左方的已知點推出）。但是三個方向就不行了，因為全是未確定點。

? ? ?
既然這樣的話我們就設(shè)置? up[i][j]，down[i][j] 分別代表從下面向上面走到（i，j），從上面向下面走到（i，j）能取到的最大值；f[i][j]表示（i，j）處最終可取到的最大值

? ?
轉(zhuǎn)移方程就好寫了：

? ? ?

up[i][j]=max(up[i+1][j],f[i][j-1])+a[i][j]；//可以從兩個方向過來

down[i][j]=max(down[i-1][j],f[i][j-1])+a[i][j]；//同理

?f[i][j]=max(up[i][j],down[i][j])；//取最大值呀

? ? ?

因為數(shù)據(jù)比較大，所以我們要壓縮成一維（因為我們在狀態(tài)轉(zhuǎn)移的時候只用到了j-1列的數(shù)據(jù)，故可以降一維，只需我們把列放外面即可。不明白的可以看動歸最開始講的那里）

? ??

故得到：//這個f[i]是上一列的，初始化時候別搞錯了

? ??
up[i]=max(up[i+1],f[i])+a[i][j]；

down[i]=max(down[i-1],f[i])+a[i][j]；

f[i]=max(up[i],down[i]) ?
? ? ?

? ? ? ?

#include <bits/stdc++.h>  //（單向）方格取數(shù)
using namespace std;//動態(tài)規(guī)劃
int n,m,a[1001][1001];
long long up[1005],down[1005],f[1005];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];f[1]=a[1][1];for(int i=2;i<=n;i++) f[i]=f[i-1]+a[i][1];//初始化第一列的每行for(int j=2;j<m;j++){//每次用上一列的數(shù)據(jù)memset(down,0,sizeof(down));//我們只需要關(guān)注行的數(shù)據(jù)即可，故需要循環(huán)一次初始化一次memset(up,0,sizeof(up));down[1]=f[1]+a[1][j];up[n]=f[n]+a[n][j];for(int i=2;i<=n;i++) down[i]=max(f[i],down[i-1])+a[i][j];for(int i=n-1;i>=1;i--) up[i]=max(f[i],up[i+1])+a[i][j];for(int i=1;i<=n;i++) f[i]=max(down[i],up[i]);//因為每列要么只向上，要么只向下，故取優(yōu)即可}f[1]+=a[1][m];//因為最后一列只能向下走，故單獨處理for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1])+a[i][m];//向下處理printf("%lld",f[n]);return 0;
}

? ? ? ?

解法二：

都說dp不好理解，那就再來個dfs吧

? ??

我們設(shè)置 f(i, j, 0)表示從下面走到該各格子(i, j)對應(yīng)最優(yōu)解，f(i, j, 1)表示從上面走到該格子對應(yīng)最優(yōu)解。

那么遞推公式：

f(i,j,0)=max（f(i+1,j,0),f(i,j-1,0),f(i,j-1,1)）
f(i,j,1)=max（f(i-1,j,1),f(i,j-1,0),f(i,j-1,1)）

? ?
? 這樣的話一共只需要跑n*m*2即可獲得所有結(jié)果，所以和dp一樣快
? ?

? ??

#include <stdio.h>
typedef long long LL;  //記憶化搜索（和dp一樣快）
const LL min_ll=-1e18;
int n,m;
LL w[1005][1005],f[1005][1005][2];
inline LL mx(LL p,LL q,LL r) {return p>q ? (p>r ? p:r) : (q>r ? q:r);}//三葉判斷最快
inline LL dfs(int x, int y, int from) {if (x<1 || x>n || y<1 || y>m) return min_ll;if (f[x][y][from] != min_ll) return f[x][y][from];//記憶化if (from == 0) f[x][y][from] = mx(dfs(x+1,y,0), dfs(x,y-1,0), dfs(x,y-1,1))+w[x][y];else f[x][y][from] = mx(dfs(x-1,y,1), dfs(x,y-1,0), dfs(x,y-1,1))+w[x][y];return f[x][y][from];
}
int main(void) {scanf("%d %d", &n, &m);for (int i=1; i<=n; ++i)for (int j=1; j<=m; ++j) {scanf("%lld", &w[i][j]);f[i][j][0]=f[i][j][1]=min_ll;}f[1][1][0]=f[1][1][1]=w[1][1];//標記終點的值，到這個狀態(tài)就直接返回，也就是dfs的結(jié)束條件printf("%lld\n",dfs(n,m,1));return 0;
}

好，那么好，如果你能看到這里，那么你真的很厲害了已經(jīng)，下面講雙向類型的。