【20CSPJ普及组】方格取数(记忆化搜索)

原题链接

题目描述
设有 n×m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入
第一行有两个整数 n,m。
接下来 n 行每行 m 个整数，依次代表每个方格中的整数。

输出
一个整数，表示小熊能取到的整数之和的最大值。

输入样例

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
1
2
3
4

输出样例

9
1

记忆化搜索的优点
本题20个测试点总耗时1400ms，单个测试点最大耗时为320ms
记忆化搜索重要的一点是搞明白每个点的状态，当然这题直接给说了，每个点可能由左上下相邻的三个方向转移而来。
搞明白每个点状态及其状态转移，写个递归函数就能AC，还是很稳的

状态表示
ll dp[N][N][3] 对于每个点(x,y)
dp[x][y][0]代表从起点到(x,y)并且是由左侧一个点转移而来
dp[x][y][1]代表从起点到(x,y)并且是由上方一个点转移而来
dp[x][y][2]代表从起点到(x,y)并且是由下方一个点转移而来

当然这三个状态可以合并成两个。 先用三个状态方便理解。

状态转移
对于dp[x][y][0] , 显然x,y 这个点是由x,y-1 向右走一格而来，
那么dp[x][y][0] = max(dp[x][y-1][0],dp[x][y-1][1],dp[x][y-1][2]) 用到了x,y-1 的三个状态

同理,对于dp[x][y][1] , 显然x,y 这个点是由x-1,y 向下走一格而来，
那么dp[x][y][1] = max(dp[x-1][y][0],dp[x-1][y][1]) 用到了x-1,y 的两个状态
其中dp[x-1][y][2] 的这个状态对于 dp[x][y][1] 是非法的 ，因为不能先从x,y 向上到 x-1,y 又从x-1,y 向下到x,y

最后对于dp[x][y][2] , x,y 由x+1,y 向上走一格而来
dp[x][y][2] = max(dp[x+1][y][0],dp[x+1][y][2]) 用到了x+1,y 的两个状态
同理 dp[x+1][y][1]这个状态对于dp[x][y][2]是非法的

时间复杂度
由于需要计算每个点的三个状态
时间复杂度为 O(nm3) 也就是 O(nm)

初始化
由于是求最大值，先对整个dp[N][N][3] 数组赋 long long 下的极小值
注意这里不建议用memset函数

初始化起点，1,1 这个点显然不能从2,1向上走一格到达，因为起点就是1,1 一开始就被到达了
因此在dp[N][N][3]数组全为极小值的情况下
单独对 dp[1][1][0] = f[1][1] ,dp[1][1] = f[1][1];

其中f[N][N]数组是 每个点的权值

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e3+10 ;
const ll MIN = -LINF;
int f[N][N];
ll dp[N][N][3];//由  右 上 下 转移而来 注意开long long
int n,m;
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<3;k++){
                dp[i][j][k] = MIN;
            }
        }
    }
}

ll dfs(int x,int y,int k){
    if(x<1 or y<1 or x>n or y>m)return MIN;//越界直接返回极小值，代表非法状态转移
    if(dp[x][y][k]!=MIN)return dp[x][y][k];//!=极小值，代表被计算过，不必重复计算直接返回

    if(k==0){//对于每个点的每个状态都有转移方程
        dp[x][y][k] = max(dfs(x,y-1,2),max(dfs(x,y-1,0),dfs(x,y-1,1))) + (ll)f[x][y];
    }
    else if(k==1){
        dp[x][y][k] = max(dfs(x-1,y,1),dfs(x-1,y,0)) + (ll)f[x][y];
    }
    else {
        dp[x][y][k] = max(dfs(x+1,y,0),dfs(x+1,y,2)) + (ll)f[x][y];
    }
    
    return dp[x][y][k];
    
}

int main() {
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&f[i][j]);
        }
    }
    init();//初始化
    dp[1][1][0] = (ll)f[1][1],dp[1][1][1] = (ll)f[1][1];

    ll ans = max(dfs(n,m,0),dfs(n,m,1)); //终点只能由左或上转移而来
    
    printf("%lld\n",ans);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56