题目大意

给定一个矩阵ｍ，从左上角开始每次都只能向下或者向右走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有路径中最小的路径和。

例如给定矩阵:

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