给定一个 n\cdot mn?m 矩阵，找一条从 (1,1)(1,1) 到 (n,m)(n,m) 权值和最大的路径，每次只准向上、下、右三个方向走。
概述：这种算法比较简单，不需要动头脑，直接三方向深搜即可。
时间复杂度：\mathcal{O}(3^{nm})O(3nm)
期望得分：2020 分
概述：考场上我只想到了这种方法（太菜了。我们设 F_{i,j,0}Fi,j,0? 表示从一个格子上方走到该格子的路径最大和，F_{i,j,1}Fi,j,1? 表示从一个格子右方走到该格子的路径最大和，F_{i,j,2}Fi,j,2? 表示从一个格子下方走到该格子的路径最大和。如果搜到相同的状态则判断是否比原 FF 值更大，如果更优则更新答案，否则退出该状态。
时间复杂度：视具体数据而定，当格子权值差值较大时能拿到较多分数。
期望得分：4040 分
#include <stdio.h> const int dx[] = {1, 0, -1}, dy[] = {0, 1, 0}; typedef long long LL; int n, m; bool vis[1005][1005]; LL w[1005][1005], f[1005][1005][3], ans = -20000000000; inline LL mx(LL p, LL q) {return p > q ? p : q;} inline void dfs(int x, int y, int from, LL now) { if (x == n && y == m) { ans = mx(now, ans); return; } if (f[x][y][from] > now) return; else f[x][y][from] = now; for (int i = 0, xx, yy; i < 3; ++i) { xx = x + dx[i]; yy = y + dy[i]; if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy]) { vis[xx][yy] = true; dfs(xx, yy, i, now + w[xx][yy]); vis[xx][yy] = false; } } } int main(void) { // freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); 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] = f[i][j][2] = -20000000000; } vis[1][1] = true; dfs(1, 1, 0, w[1][1]); printf("%lld\n", ans); return 0; }
概述：这才是正解。我们设 F_{i,j,0}Fi,j,0? 表示从一个格子上方走到该格子的路径最大和，F_{i,j,1}Fi,j,1? 表示从一个格子下方走到该格子的路径最大和。如果搜到以前搜过的状态则直接返回搜过的最大和（也就是 FF 中的值），否则继续搜索到达该格时的最大和。
时间复杂度：\mathcal{O}(nm)O(nm)
期望得分：100100 分
#include <stdio.h> typedef long long LL; 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) { // freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); 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]; printf("%lld\n", dfs(n, m, 1)); return 0; }
原文：https://www.cnblogs.com/pxy071128fzm/p/14032256.html