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;}}