P7074 [CSP-J2020] 方格取数 题解

题目：

题目描述

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

输入格式

第一行有两个整数 n, m。

接下来 n 行每行 m 个整数，依次代表每个方格中的整数。

输出格式

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

 1 #include<bits/stdc++.h>
 2 #define maxn 1001
 3 using namespace std;
 4 int grid[maxn][maxn],dp[maxn][maxn];
 5 int main()
 6 {
 7     int n, m;
 8     cin >> n >> m;
 9     for(int i=1;i<=n;++i)
10     {
11         for(int j=1;j<=m;++j)
12         {
13             cin>>grid[i][j];
14         }
15     }
16     
17     dp[1][1] = grid[1][1];
18     for(int i=2;i<=n;++i)
19     {
20         dp[i][1]=dp[i-1][1]+grid[i][1];
21     }
22     for(int j=2;j<=m;++j)
23     {
24         int t=INT_MIN;
25         for(int i=1;i<=n;++i)
26         {
27             t=max(t,dp[i][j-1])+grid[i][j],dp[i][j]=max(t,dp[i][j]);
28         }  
29         t=INT_MIN;
30         for(int i=n;i>0;--i)
31         {
32             t=max(t,dp[i][j-1])+grid[i][j],dp[i][j]=max(t,dp[i][j]);
33         }
34     }
35     cout << dp[n][m] << endl;
36     return 0;
37 }