查找從最上一行向下一行向下移動的最大總和路徑

Question

我正在從「Java照明」一書中做遞歸章節問題。我需要在正整數的矩形網格中找到總和最大的路徑，從最上一行的任意位置開始，然後在每個後續步驟中直接向下或向下移動。

到目前爲止，我已經能夠計算出最大路徑的實際總和。在下面的網格

02 05 17 12 03 
15 08 04 11 10 
09 18 06 20 16 
14 13 12 01 07 

我現有的代碼將返回60

我怎樣才能返回（或打印出）與最大和的路徑？即17 + 11 + 20 + 12 = 60

public class MaximumPath { 

    public static int maxSum(int grid[][]){ 
     int r = grid.length - 1;  // bottom row # 
     int c = grid[0].length - 1;  // rightmost column # 
     int max = 0; 
     for (int i=0; i <= c; i++){ 
      int val = maxSum(grid, r, i); // call recursive method for each of the bottom row cells 
      if (val > max) max = val; 
     } 
     return max; 
    } 

    public static int maxSum(int grid[][], int row, int col) 
    // recursive method to find largest sum path to row,col, coming downwards from top 
    { 
     if (col < 0 || row < 0 || row > grid[0].length || col > grid.length) return 0;  
     else return grid[row][col] + max3( maxSum(grid, row-1, col-1),   // top left 
              maxSum(grid, row-1, col),   // top 
              maxSum(grid, row-1, col+1)) ;  // top right 
    } 

    public static int max3(int x, int y, int z) // return max of 3 numbers 
    { 
     if (x > y) 
      return (x > z)? x : z; 
     else 
      return (y > z)? y : z; 
    } 

    public static void main(String[] args){ 
     int[][] grid = {{2, 5, 17, 12, 3}, 
         {15, 8, 4, 11, 10}, 
         {9, 18, 6, 20, 16}, 
         {14, 13, 12, 1, 7}}; 
     System.out.println("Max sum is "+maxSum(grid)); 
    } 
} 

Answer 1

你的問題是，由於遞歸的性質，你不知道哪個路徑是正確的，直到最後。因此，您必須隨時存儲每條路徑（包括總數），只保留每行比較中的最大路徑。

這裏是一個快速解決方案，我掀起了：

import java.util.*; 

public class MaximumPath { 

    // object to store both path and total 
    public static class Pair { 
     public ArrayList a; 
     public int b; 

     public Pair(ArrayList a, int b) { 
      this.a = a; 
      this.b = b; 
     } 
    }; 

    public static Pair maxSum(int grid[][]){ 
     int r = grid.length - 1;  // bottom row # 
     int c = grid[0].length - 1;  // rightmost column # 
     Pair max = null; 
     for (int i=0; i <= c; i++){ 
      Pair val = maxSum(grid, r, i); // call recursive method for each of the bottom row cells 
      if (max == null || val.b > max.b) max = val; 
     } 
     return max; 
    } 

    public static Pair maxSum(int grid[][], int row, int col) 
    // recursive method to find largest sum path to row,col, coming downwards from top 
    { 
     if (col < 0 || row < 0 || row > grid[0].length || col > grid.length){   
      return new Pair(new ArrayList(), 0);   
     }else{ 
      // take the path pair with the max value so far 
      Pair p = maxPair(maxSum(grid, row-1, col-1),   // top left 
          maxSum(grid, row-1, col),   // top 
          maxSum(grid, row-1, col+1)) ;  // top right)    
      // add the current path value and total to the path 
      p.a.add(grid[row][col]); 
      p.b += grid[row][col];   
      return p; 
     }  
    } 

    public static Pair maxPair(Pair x, Pair y, Pair z) 
    { 
     if(x.b > y.b){ 
      return (x.b > z.b)? x : z; 
     }else{ 
      return (y.b > z.b)? y : z; 
     }   
    } 

    public static void main(String[] args){ 
     int[][] grid = {{2, 5, 17, 12, 3}, 
         {15, 8, 4, 11, 10}, 
         {9, 18, 6, 20, 16}, 
         {14, 13, 12, 1, 7}};  
     Pair p = maxSum(grid); 
     System.out.println("Max sum is " + p.b); 
     System.out.println("Path is " + p.a); 
    } 
} 

Answer 2

這是一個典型的編程問題。你需要找到Maximum Subarray。

Wiki涵蓋了一維的算法。一旦你明白了這一點，它很容易擴展到2維。