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.
Пример:
Вход: grid = [[1,3,1],[1,5,1],[4,2,1]] Выход: 7
Мой код проходит все тесты кроме последней и выдаёт Time Limit Exceeded.
class Solution {
private int minPath = Integer.MAX_VALUE;
private int minPathSum(int[][] grid, int currentSum, int i, int j) {
if (currentSum > minPath)
return minPath;
if (i == grid.length - 1 && j == grid[0].length - 1) {
minPath = currentSum;
return minPath;
}
int right = Integer.MAX_VALUE, bottom = Integer.MAX_VALUE;
if (i < grid.length - 1)
bottom = minPathSum(grid, currentSum + grid[i + 1][j], i + 1, j);
if (j < grid[0].length - 1)
right = minPathSum(grid, currentSum + grid[i][j + 1], i, j + 1);
return right > bottom ? bottom : right;
}
public int minPathSum(int[][] grid) {
return minPathSum(grid, grid[0][0], 0, 0);
}
} 
