Acwing1015. 摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
$1\le T\le 100$,
$1\le R,C\le 100$,
$0\le M\le 1000$

---

注意：在平时解决数学问题时，直角坐标系通常是x轴指向右侧，y轴指向上方；但是在算法题目中一旦出现直角坐标系，通常是x轴指向右侧，y轴指向下方。

---

本题目使用动态规划法进行求解，通过闫氏DP分析法进行分析：
状态表示：f[i][j]

• 集合：从（0，0）走到（i，j）的所有的路径所取得的花生数目。
• 属性：MAX

状态计算：以最后一步的之前一步进行分割–>分为从左来和从上来；

• 状态方程：f[i, j] = max(f[i-1, j], f[i, j-1]) + w[i, j]

代码：

java运行本题时，Scanner会超时，这里我们将使用BufferReader，速度将会有极大的提升。

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		while(T -- > 0) {
			String[] arr = br.readLine().split(" ");
			int row = Integer.parseInt(arr[0]);
			int col = Integer.parseInt(arr[1]);
			int [][]a = new int[row+2][col+2];
			for(int i = 1; i <= row; ++i) {
				String[] ar = br.readLine().split(" ");
				for(int j = 1; j <= col; ++j) {
					a[i][j] = Integer.parseInt(ar[j-1]);
				}
			}
			int [][]dp = new int[row+2][col+2];
			for(int i = 1; i <= row; ++i) {
				for(int j = 1; j <= col; ++j) {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])+a[i][j];
				}
			}
			System.out.println(dp[row][col]);
		}
	}
 }
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

做完了