Кажется, мемоизация работает не так, как задумано

Question

Проблема, которую я пытаюсь решить:

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];
        }
    }
}

Однако мой запомнившийся алгоритм не работает для случая [[1,3,1], [1,5,1], [4,2,1]], ожидаемый результат которого равен 7.Мой неэффективный рекурсивный алгоритм возвращает 7. Однако мой запомнившийся алгоритм возвращает неправильный ответ 9. Кажется, я не могу понять, почему это так.Я всегда делал пометки, как это, и странно, что он возвращает неправильный ответ.

Answer 1

Вы не должны передавать переменную суммы в вашем методе вообще.Вы вводите:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

, и изначально ваша заметка:

[
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

Самая первая ячейка в заметке, которая будет рассчитана, равна (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)