8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

如何计算矩阵中从 [0,0] 到 [M, N] 的最小和路径?

rustyMagnet 2月前

52 0

我需要计算从 [0,0] 到 [M, N] 的路径,矩阵中的最小和仅向右或向下移动?我发现这样的链接https://www.programcreek.com/2014/05/leetcode-minimum-path-sum-java/但是动态

我需要计算从 [0,0] 到 [M, N] 的路径,其中矩阵中的最小和仅向右或向下移动?

我找到了这样的链接 https://www.programcreek.com/2014/05/leetcode-minimum-path-sum-java/ ,但是动态规划选项根本不清楚。

我尝试用 BFS 算法自己实现它,但这是一个缓慢的解决方案

public int minPathSum(final int[][] grid) {
        if (grid.length == 1 && grid[0].length == 1) {
            return grid[0][0];
        }
        final int[][] moves = {new int[]{1, 0}, new int[]{0, 1}};
        final Queue<int[]> positions = new ArrayDeque<>();
        final Queue<Integer> sums = new ArrayDeque<>();
        positions.add(new int[]{0, 0});
        sums.add(grid[0][0]);
        int minSum = Integer.MAX_VALUE;
        while (!positions.isEmpty()) {
            final int[] point = positions.poll();
            final int sum = sums.poll();
            for (final int[] move : moves) {
                final int x = point[0] + move[0];
                final int y = point[1] + move[1];
                if (x == grid.length - 1 && y == grid[0].length - 1) {
                    minSum = Math.min(minSum, sum);
                } else if (x > -1 && y > -1 && x < grid.length && y < grid[0].length) {
                    positions.add(new int[]{x, y});
                    sums.add(sum + grid[x][y]);
                }
            }
        }
        return minSum + grid[grid.length - 1][grid[0].length - 1];
    }

您能否解释一下并尽可能提供您将如何解决该问题?

帖子版权声明 1、本帖标题:如何计算矩阵中从 [0,0] 到 [M, N] 的最小和路径?
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由rustyMagnet在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 这些点之间的线是矩形的对角线。所以你的路径将是这个矩形周长的一半。我说得对吗?

  • 最简单的方法可能是使用递归函数,通过递归计算两种可能性中的最小值。矩阵有多大?

  • 我对于如何实现广度优先搜索有点困惑,但无法理解这里的动态公式,对我来说这似乎更简单:)

    这几乎是经典的动态规划问题。到达 solution[y][x] 除第一个之外的任何单元格,最多有两个前身: option 1 option 2 。假设我们知道到达每个单元格的最佳解决方案,我们会选择哪条边?显然是两个选项中更好的一个!

    更正式地说,如果 M 保存给定的值:

    solution[0][0] = M[0][0]
    
    // only one choice along
    // the top horizontal and
    // left vertical
    
    solution[0][x] =
      M[0][x] + solution[0][x - 1]
    
    solution[y][0] =
      M[y][0] + solution[y - 1][0]
    
    // two choices otherwise:
    // the best of option 1 or 2
    
    solution[y][x] =
      M[y][x] + min(
        solution[y][x - 1],
        solution[y - 1][x]
      )
    

    我们可以看到,我们可以创建一个适当的例程,例如使用 for 以“自下而上”的顺序 solution 访问矩阵的单元,

    JavaScript 代码:

    function show(M){
      let str = '';
      for (let row of M)
        str += JSON.stringify(row) + '\n';
      console.log(str);
    }
    
    function f(M){
      console.log('Input:\n');
      show(M);
      
      let solution = new Array();
      for (let i=0; i<M.length; i++)
        solution.push(new Array(M[0].length).fill(Infinity));
        
      solution[0][0] = M[0][0];
    
      // only one choice along
      // the top horizontal and
      // left vertical
      
      for (let x=1; x<M[0].length; x++)
        solution[0][x] =
          M[0][x] + solution[0][x - 1];
    
      for (let y=1; y<M.length; y++)
        solution[y][0] =
          M[y][0] + solution[y - 1][0];
          
      console.log('Solution borders:\n');
      show(solution);
    
      // two choices otherwise:
      // the best of option 1 or 2
    
      for (let y=1; y<M.length; y++)
        for (let x=1; x<M[0].length; x++)
          solution[y][x] =
            M[y][x] + Math.min(
              solution[y][x - 1],
              solution[y - 1][x]
            );
            
      console.log('Full solution:\n');
      show(solution);
      
      return solution[M.length-1][M[0].length-1];
    }
    
    let arr = [];
    arr[0] = [0, 7, -7];
    arr[1] = [6, 7, -8];
    arr[2] = [1, 2, 0];
    
    console.log(f(arr));
  • 那么你的意思是简单地选择每一步的最小值吗?哪一个单元格包含负值?如果矩阵是: arr[0] = {0, 7, -7}, arr[1] = {6, 7, -8}, arr[2] = {1, 2, 0} 怎么办?

  • 您的解决方案不支持它,因为 min() 单元格后的下一个单元格可以是正值,但 greater 单元格后的下一个单元格可以是负值

  • @Pavel 我不明白。你能举个例子说明它是如何失败的吗?这个公式是纯数学的。

  • arr[0] = {0, 7, -7}, arr[1] = {6, 7, -8}, arr[2] = {1, 2, 0}

  • 到达 (m, n) 的路径必须经过以下两个单元格之一:(m-1, n) 或 (n-1, m)。因此,到达 (m, n) 的最小和可以写为“两个单元格中的最小值加上 sum[m][n]”。

    minSum(m, n) = min (minSum(m-1, n-1), minSum(m-1, n)) + sums[m][n]
    
  • 那么你的意思是简单地选择每一步的最小值吗?哪一个单元格包含负值?如果矩阵是: arr[0] = {0, 7, -7}, arr[1] = {6, 7, -8}, arr[2] = {1, 2, 0} 怎么办?

返回
作者最近主题: