欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 12:10:27
...

题目:

输入一个矩阵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

输出

17


分析:

方法一、采用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();
	}
}


相关标签: dfs 动态规划