AcWing 1015. 摘花生

Problem: AcWing 1015. 摘花生

思路

这是一个典型的动态规划问题。我们需要在一个二维网格中，从左上角走到右下角，每次只能向右或向下移动，目标是使得经过的路径上的数字之和最大。
我们可以定义dp[i][j]为从左上角走到(i, j)位置，能够得到的最大数字之和。然后我们可以根据dp[i - 1][j]和dp[i][j - 1]来更新dp[i][j]。

解题方法

我们首先初始化dp数组，然后从左上角开始，遍历每一个位置，对于每一个位置，我们都有从上面来和从左边来两种情况：如果我们从上面来，那么dp[i][j] = dp[i - 1][j] + w[i][j]。如果我们从左边来，那么dp[i][j] = dp[i][j - 1] + w[i][j]。我们取这两种情况的最大值，就是dp[i][j]的值。最后，dp[r][c]就是我们的答案。

复杂度

时间复杂度:

$O(rc)$，因为我们需要遍历每一个位置。

空间复杂度:

$O(rc)$，因为我们需要一个二维数组来存储dp值。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int t, r, c, m;
	static int MAXN = 110;
	static int[][] dp = new int[MAXN][MAXN];
	static int[][] w = new int[MAXN][MAXN];

	public static void main(String[] args) throws IOException {
		t = nextInt();
		while (t-- > 0) {
			r = nextInt();
			c = nextInt();
			for (int i = 1; i <= r; i++) {
				for (int j = 1; j <= c; j++) {
					w[i][j] = nextInt();
				}
			}
			for (int i = 1; i <= r; i++) {
				for (int j = 1; j <= c; j++) {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + w[i][j];
				}
			}

			out.println(dp[r][c]);
		}
		out.flush();

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}