Динамическое программирование минимальной суммы пути по сетке ⇐ JAVA

[Anonymous]

Недавно я обнаружил в своем коде досадную ошибку. У меня есть два решения для поиска минимальной суммы путей с помощью динамического программирования (DP). Первое решение, которое я написал, похоже, не работает, хотя логика кажется идеальной. Вот мой код:

Код: Выделить всё

class Solution {
public int minPathSum(int[][] arr) {
return f(arr.length-1, arr[0].length-1, arr);
}

public int f(int i, int j, int[][] arr) {
if (i < 0 || j < 0) return Integer.MAX_VALUE;
if (i == 0 && j == 0) return arr[0][0];
int up = arr[i][j] + f(i-1, j, arr);
int left = arr[i][j] + f(i, j-1, arr);
return Math.min(up, left);
}
}

Однако я нашел в Интернете другое работающее решение:

Код: Выделить всё

class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length-1;
int n = grid[0].length-1;
return find(grid, m, n);
}

public int find(int grid[][], int m, int n) {
if (m < 0 || n < 0) return Integer.MAX_VALUE;
if (m == 0 && n == 0) return grid[0][0];
return grid[m][n] + Math.min(find(grid, m-1, n), find(grid, m, n-1));
}
}

Единственная разница между моим решением и рабочим решением заключается в том, как мы возвращаем результат. В своем решении я использовал up и left для сохранения результата рекурсивных вызовов с текущим значением пути, а позже выбрал минимальный путь. Однако в рабочем решении все делается за один шаг. В чем разница между этими двумя? Пожалуйста, разъясните мои сомнения.

Подробнее здесь: https://stackoverflow.com/questions/783 ... h-grid-sum