/
githubmirror
/
interviews
Обзор
Документация
Войти
/
githubmirror
/
interviews
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
leetcode/array/MinimumPathSum.java
27 строк
913 B
Kevin Naughton Jr
add MinimumPathSum
29 май 2018, 20:20
29 май 2018, 20:20
6830e7c
Код
Авторство
О чём код?
//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 1: //[[1,3,1], //[1,5,1], //[4,2,1]] //Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum. class MinimumPathSum { public int minPathSum(int[][] grid) { for(int i = 1; i < grid.length; i++) { grid[i][0] += grid[i - 1][0]; } for(int i = 1; i < grid[0].length; i++) { grid[0][i] += grid[0][i - 1]; } for(int i = 1; i < grid.length; i++) { for(int j = 1; j < grid[0].length; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[grid.length - 1][grid[0].length - 1]; } }