题目大意
给定一个矩阵m,从左上角开始每次都只能向下或者向右走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有路径中最小的路径和。
例如给定矩阵:
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
路径1,3,1,0,6,1,0是所有路径中和最小的,所以返回12
分析
我想到的是 dfs 剪枝,非右即下 判断 右下两值大小 做出选择。
但是 有个问题 万一 他俩相同怎么办? 这种解法只能过 数据较小 且没重复选择的测试点
代码
wa dfs
package BlueCup.Seven_recursion.Test;
import java.util.Scanner;
public class 矩阵的最小路径和 {
static int a[][];
static int m, n;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
m = cin.nextInt();
n = cin.nextInt();
a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = cin.nextInt();
}
}
dfs(0, 0);
System.out.println(sum);
}
static int sum = 0;
private static void dfs(int x, int y) {
sum += a[x][y];
if (x == m - 1 || y == n - 1) {
return;
}
if (a[x + 1][y] > a[x][y + 1]) {
dfs(x, y + 1);
} else {
dfs(x + 1, y);
}
}
}
AC DP
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] nums = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
nums[i][j] = sc.nextInt();
}
}
int[][] dp = new int[n][m];
dp[0][0] = nums[0][0];
for(int i=1;i<n;i++){
dp[i][0] = nums[i][0] + dp[i-1][0];
}
for(int i=1;i<m;i++){
dp[0][i] = nums[0][i] + dp[0][i-1];
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + nums[i][j];
}
}
System.out.println(dp[n-1][m-1]);
}
}
优化
package BlueCup.Seven_recursion.Test;
import java.util.Scanner;
public class 矩阵的最小路径和 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
for (int i = 1; i < n; i++) {
a[i][0]+=a[i-1][0];
}
for (int i = 1; i < m; i++) {
a[0][i]+=a[0][i-1];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
a[i][j] += Math.min(a[i - 1][j], a[i][j - 1]) ;
}
}
System.out.println(a[n - 1][m - 1]);
}
}
类似的题
一个m*n的矩阵,只能向右走或是向下走,矩阵每一个元素代表一个财富值,要求打印出从左上角到右下角走的财富最大总值。
如输入m=4 ,n=5,
输入矩阵value=
{ 0 0 7 0 0,
0 0 0 5 0,
2 0 4 0 0,
0 0 0 3 0},
打印出最大财富总值是15。
这是动态规划的题目,跟“[leetcode 64] Minimum Path Sum------从左上角到右下角的最小路径值”的思路是一样的,
oj
牛客 https://www.nowcoder.com/questionTerminal/2fb62a4500af4f4ba5686c891eaad4a9
本文地址:https://dxoca.cn/Algorithm/236.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
云外创想网络工作室 :
dfs一般是对数组array元素进行讨论
dp则直接对限定值s进行讨论