解法一:二维dp,状态转移方程为:dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + f[i][j];
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while (count-- > 0) {
int m = sc.nextInt(), n = sc.nextInt();
int[][] f = new int[m + 1][n + 1];
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n ; j++) {
f[i][j] = sc.nextInt();
}
}
dp[1][1] = f[1][1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n ; j++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + f[i][j];
}
}
System.out.println(dp[m][n]);
}
}
}
解法二:利用滚动数组优化空间复杂度
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while (count-- > 0) {
int m = sc.nextInt(), n = sc.nextInt();
int[][] f = new int[m + 1][n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = sc.nextInt();
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[j] = Math.max(dp[j - 1], dp[j]) + f[i][j];
}
}
System.out.println(dp[n]);
}
}
}