【蓝桥每日一题]-动态规划 （保姆级教程 篇10）#方格取数

高能预警：讲了这么久动态规划了，该上点有难度的题吧

目录

题目：方格取数

 思路（解法一）：

 解法二：

---

题目：方格取数

        

 思路（解法一）：

如果只有两个方向的话，动态规划就很简单了，因为很容易就能根据已确定点推出未确定点（因为每个未知点都可以由上方和左方的已知点推出）。但是三个方向就不行了，因为全是未确定点。

     
既然这样的话我们就设置  up[i][j]，down[i][j] 分别代表从下面向上面走到（i，j），从上面向下面走到（i，j）能取到的最大值；f[i][j]表示（i，j）处最终可取到的最大值

   
转移方程就好写了：

     

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])；//取最大值呀

     

因为数据比较大，所以我们要压缩成一维（因为我们在状态转移的时候只用到了j-1列的数据，故可以降一维，只需我们把列放外面即可。不明白的可以看动归最开始讲的那里）

    

故得到：//这个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>  //（单向）方格取数
using namespace std;//动态规划
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++){//每次用上一列的数据memset(down,0,sizeof(down));//我们只需要关注行的数据即可，故需要循环一次初始化一次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]);//因为每列要么只向上，要么只向下，故取优即可}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吧

    

我们设置 f(i, j, 0)表示从下面走到该各格子(i, j)对应最优解，f(i, j, 1)表示从上面走到该格子对应最优解。

那么递推公式：

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即可获得所有结果，所以和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];//标记终点的值，到这个状态就直接返回，也就是dfs的结束条件printf("%lld\n",dfs(n,m,1));return 0;
}

好，那么好，如果你能看到这里，那么你真的很厉害了已经，下面讲双向类型的。