站长工具网址查询,ui设计师培训费用,天津网络广告公司,附近找工作8小时长白班高能预警#xff1a;讲了这么久动态规划了#xff0c;该上点有难度的题吧
目录
题目#xff1a;方格取数 思路#xff08;解法一#xff09;#xff1a; 解法二#xff1a; 题目#xff1a;方格取数 思路#xff08;解法一#xff09;#xff1a; 如果只有两个方向…高能预警讲了这么久动态规划了该上点有难度的题吧
目录
题目方格取数 思路解法一 解法二 题目方格取数 思路解法一 如果只有两个方向的话动态规划就很简单了因为很容易就能根据已确定点推出未确定点因为每个未知点都可以由上方和左方的已知点推出。但是三个方向就不行了因为全是未确定点。 既然这样的话我们就设置 up[i][j]down[i][j] 分别代表从下面向上面走到ij从上面向下面走到ij能取到的最大值f[i][j]表示ij处最终可取到的最大值 转移方程就好写了 up[i][j]max(up[i1][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[i1],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(){cinnm;for(int i1;in;i)for(int j1;jm;j)cina[i][j];f[1]a[1][1];for(int i2;in;i) f[i]f[i-1]a[i][1];//初始化第一列的每行for(int j2;jm;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 i2;in;i) down[i]max(f[i],down[i-1])a[i][j];for(int in-1;i1;i--) up[i]max(f[i],up[i1])a[i][j];for(int i1;in;i) f[i]max(down[i],up[i]);//因为每列要么只向上要么只向下故取优即可}f[1]a[1][m];//因为最后一列只能向下走故单独处理for(int i2;in;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)maxf(i1,j,0),f(i,j-1,0),f(i,j-1,1) f(i,j,1)maxf(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 pq ? (pr ? p:r) : (qr ? q:r);}//三叶判断最快
inline LL dfs(int x, int y, int from) {if (x1 || xn || y1 || ym) return min_ll;if (f[x][y][from] ! min_ll) return f[x][y][from];//记忆化if (from 0) f[x][y][from] mx(dfs(x1,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 i1; in; i)for (int j1; jm; 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;
}
好那么好如果你能看到这里那么你真的很厉害了已经下面讲双向类型的。
