从矩阵左上角到右下角的最大值

科技前沿 • 2025-02-24 18:48 • 阅读 25

大家好，我是讯享网，很高兴认识大家。

题目：

输入一个矩阵M×N，现在从左上角到达右下角，且只能向下或者向右走。我们要求的是路径经过的所有点的数字之和的最大值。

输入输出示例：

输入数据：

第一行有两个数字M和N，表示这个矩阵有M行N列。

然后从第二行开始，有M行整数，每行都有N个非负整数。

输出数据：

所过路径的最大和。

数据范围：0<M,N<=1000，矩阵中的字数不会超过1000

示例：

输入

4 5

讯享网

0 0 8 0 0

0 0 0 9 0

0 7 0 0 0

0 0 6 0 0

输出

分析：

方法一、采用DFS的思想

import java.util.*; public class MaxMatrixPathSum { private static int M; private static int N; private static int[][] A; public static int dfs(int i, int j) { if(i == M || j == N) return 0; else if(i == M-1 && j == N-1) return A[i][j]; else return max(dfs(i+1, j), dfs(i, j+1)) + A[i][j]; } public static int max(int i, int j) { return i > j ? i : j; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { M = sc.nextInt(); N = sc.nextInt(); A = new int[M][N]; for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { A[i][j] = sc.nextInt(); } } System.out.println(dfs(0, 0)); } } }

讯享网
方法二、采用动态规划的思想

讯享网import java.util.Scanner; public class MaxMatrixPath { public static int getMaxPathSum(int[][] nums) { if(nums == null || nums.length == 0) return 0; int M = nums.length; int N = nums[0].length; int dp[][] = new int[M][N]; for(int j = 0; j < N; j++) { for(int i = 0; i < M; i++) { if(i == 0 && j == 0) { dp[i][j] = nums[i][j]; continue; } if(j == 0) { dp[i][j] = dp[i-1][j] + nums[i][j]; continue; } if(i == 0) { dp[i][j] = dp[i][j-1] + nums[i][j]; continue; } dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + nums[i][j]; } } return dp[M-1][N-1]; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int M = sc.nextInt(); int N = sc.nextInt(); int[][] nums = new int[M][N]; for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { nums[i][j] = sc.nextInt(); } } System.out.println(getMaxPathSum(nums)); } sc.close(); } }

从矩阵左上角到右下角的最大值

相关推荐