Дан массив, содержащий неотрицательные целые числаm x nСетка, найдите путь из левого верхнего угла в правый нижний угол, чтобы сумма чисел на пути была наименьшей.
**Примечание.** Вы можете перемещаться вниз или вправо только на один шаг за раз.
Пример:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
Вчера я задавал вопрос по алгоритму и чувствую, что рисование изображения очень помогает мне понять процесс работы алгоритма На этот раз я выберу другой алгоритм, чтобы усилить свое впечатление. Столкновение с этим типом проблемы очень похоже на рекурсию, но с рекурсией, если диапазон данных относительно велик, это займет много времени.
динамическое программирование(Английский: динамическое программирование, именуемое DP) — это метод, используемый в математике, менеджменте, информатике, экономике и биоинформатике для решения сложных проблем путем разложения исходной проблемы на относительно простые подзадачи.динамическое программированиеЧасто подходит для задач с перекрывающимися подзадачами и оптимальными свойствами подструктуры,динамическое программированиеМетод часто намного меньше времени, затрачиваемого на простое решение.
Без дальнейших церемоний
решение проблем
По смыслу вопроса достижение определенной точки в сетке является кратчайшим, что можно понимать как то, что любую точку в сетке можно обойти, и любая сетка имеет кратчайший путь.
Затем мы используем структуру данных, чтобы сохранить кратчайшую позицию от вершины до любой точки сетки. Согласно нормальной человеческой логике рисунок выглядит следующим образом:
- Пройдите каждую позицию в строках из вершин и рассчитайте минимальный путь для каждой позиции.
Основываясь на картинке выше:
- когда
点Когда он находится в первой строке, его кратчайший путь — это предыдущая позиция в той же строке плюс текущая позиция. - когда
点Когда он находится в первом столбце, его кратчайший путь — это позиция предыдущей строки плюс текущая позиция. - когда
点Когда в вершине, это значение вершины - когда
点В середине это минимальное значение предыдущей строки или столбца плюс текущее значение.
На данный момент мы написали программу следующим образом:
public static int minPathSumAi(int[][] grid){
// 特殊情况处理
if (grid.length == 0){
return 0;
}
// 新建一个标记数组，标记到每个位置的最短路径
int xLen = grid.length;
int yLen = grid[0].length;
int[][] markBit = new int[xLen][yLen];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
// 初始位置
if (i == 0 && j == 0){
markBit[i][j] = grid[i][j];
}
// 当点在第一行的位置时
else if (i == 0){
markBit[i][j] = markBit[i][j-1] + grid[i][j];
}
// 当点在第一列的位置时
else if (j == 0){
markBit[i][j] = markBit[i-1][j] + grid[i][j];
}
// 当点在数组的中间位置时
else {
markBit[i][j] = Math.min(markBit[i-1][j] , markBit[i][j-1]) + grid[i][j];
}
}
}
return markBit[xLen-1][yLen-1];
}
Затем протестируйте LeetCode, производительность должна быть улучшена, а затем придумайте лучшее решение после улучшения следующего уровня.В настоящее время поймите метод решения проблем.
наконец
Запуском программы управляют люди.Перед запуском программы убедитесь, что ваша собственная логика понятна.Рисование может помочь вам прояснить логику.