我要解决的问题是：
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum
所以，这是我可以使用的递归实现：
class Solution {
public int minPathSum(int[][] grid) {
int[][] memo = new int[grid.length][grid[0].length];
return minPathSum(grid, 0, 0, 0, memo);
}
public int minPathSum(int[][] grid, int i, int j, int sum, int[][] memo) {
if(i == grid.length-1 && j == grid[0].length-1) {
return sum+grid[i][j];
}
else if(i>=grid.length || j >= grid[0].length) {
return 10000;
}
else {
return Math.min(minPathSum(grid,i+1,j,sum+grid[i][j], memo), minPathSum(grid,i,j+1,sum+grid[i][j], memo));
}
}
}
然后是记忆算法：
class Solution {
public int minPathSum(int[][] grid) {
int[][] memo = new int[grid.length][grid[0].length];
return minPathSum(grid, 0, 0, 0, memo);
}
public int minPathSum(int[][] grid, int i, int j, int sum, int[][] memo) {
if(i == grid.length-1 && j == grid[0].length-1) {
return sum+grid[i][j];
}
else if(i>=grid.length || j >= grid[0].length) {
return 10000;
}
else {
if(memo[i][j] == 0)
memo[i][j] = Math.min(minPathSum(grid,i+1,j,sum+grid[i][j], memo), minPathSum(grid,i,j+1,sum+grid[i][j], memo));
return memo[i][j];
}
}
}
但是，对于期望输出为7的[[1,3,1]、[1,5,1]、[4,2,1]]情况，我的记忆算法失败。我的无效递归算法返回7然而，我的记忆算法返回了错误的答案9我好像找不到原因。我一直都是这样做的，奇怪的是它返回了错误的答案。
最佳答案
您根本不应该在方法中传递sum变量。您的输入是：
[
[1,3,1],
[1,5,1],
[4,2,1]
]
最初你的备忘录是，
[
[0,0,0],
[0,0,0],
[0,0,0]
]
memo中第一个要计算的单元格是（2,2），它总共有9个，因为它计算路径（0,0）—>（1,0）—>（2,0）—>（2,1）的答案，然后是（2,2）。但这是错误的，因为它应该只保存表示子网格的最小答案的值。
试着像这样使用备忘录，
public int minPathSum(int[][] grid, int i, int j, int[][] memo) {
if(i == grid.length-1 && j == grid[0].length-1) {
memo[i][j] = grid[i][j];
return grid[i][j];
}
else if(i>=grid.length || j >= grid[0].length) {
return 10000;
}
else {
int val = grid[i][j]+Math.min(minPathSum(grid,i+1,j, memo), minPathSum(grid,i,j+1, memo));
if(memo[i][j] > val || memo[i][j] == 0){
memo[i][j] = val;
}
for(int k = 0;k<memo.length;k++){
System.out.println(Arrays.toString(memo[k]));
}
System.out.println("i:"+i+" j:"+j);
return memo[i][j];
}
}
示例运行将提供以下输出：
[0, 0, 0]
[0, 0, 0]
[0, 3, 1]
i:2 j:1
[0, 0, 0]
[0, 0, 0]
[7, 3, 1]
i:2 j:0
[0, 0, 0]
[0, 0, 0]
[7, 3, 1]
i:2 j:1
[0, 0, 0]
[0, 0, 2]
[7, 3, 1]
i:1 j:2
[0, 0, 0]
[0, 7, 2]
[7, 3, 1]
i:1 j:1
[0, 0, 0]
[8, 7, 2]
[7, 3, 1]
i:1 j:0
[0, 0, 0]
[8, 7, 2]
[7, 3, 1]
i:2 j:1
[0, 0, 0]
[8, 7, 2]
[7, 3, 1]
i:1 j:2
[0, 0, 0]
[8, 7, 2]
[7, 3, 1]
i:1 j:1
[0, 0, 0]
[8, 7, 2]
[7, 3, 1]
i:1 j:2
[0, 0, 3]
[8, 7, 2]
[7, 3, 1]
i:0 j:2
[0, 6, 3]
[8, 7, 2]
[7, 3, 1]
i:0 j:1
[7, 6, 3]
[8, 7, 2]
[7, 3, 1]
i:0 j:0
7
每个单元格都包含子网格的答案，子网格的单元格是最上面和最左边的元素。稍后，如果单元格最初没有更新（即cellvalue==0），或者如果新找到的解决方案小于当前解决方案（即cellvalue>new answer），则更新单元格