В этой задаче на Литкоде нам нужно вычислить стоимость минимального пути, учитывая следующую задачу:
Учитывая квадратный массив целых чисел
A
, нам нужна минимальная сумма падающего пути черезA
.
Падающий путь начинается с любого элемента в первой строке и выбирает по одному элементу из каждой строки. Выбор следующей строки должен находиться в столбце, который отличается от столбца предыдущей строки не более чем на единицу.
Эта проблема обычно относится к тому типу проблем, которые решаются с помощью динамического программирования. Если вы не знаете, что такое динамическое программирование, не проблема, мы пройдем его вместе. Причина, по которой вы можете догадаться, что это решаемо с помощью динамического программирования, заключается в том, что:
- Количество путей экспоненциально зависит от количества строк (размер задачи)
- Существует простое рекуррентное соотношение между стоимостью доступа к «соседним» пространствам, позволяющее легко вычислить стоимость минимальных путей для строки, учитывая стоимость минимальных путей из предыдущей строки.
На примере, предоставленном вместе с задачей, покажем, как работает алгоритм:
Шаг 1: Инициализация массива S (решения) с первой строкой A
Шаг 2: вычислить вторую строку
Шаг 3: Третий ряд
Шаг 4: выберите минимум из последней строки
Формально рекуррентная формула, которую мы используем для решения этой задачи:
S[i][j] = A[i][j] + min( S[i - 1][j - 1], S[i - 1][j], S[i - 1][j + 1])
Мы используем эту формулу для построения S построчно, затем выбираем минимум для последней строки, которая соответствует искомому решению.
Java-код:
class Solution { public int minFallingPathSum(int[][] A) { int n = A.length; if (n == 1) { return A[0][0]; } int[][] s = new int[n][n]; for (int i = 0; i < n; i++) { s[0][i] = A[0][i]; } for (int j = 1; j < n; j++) { for (int i = 0; i < n; i++) { if (i == 0) { s[j][i] = Math.min( s[j - 1][i], s[j - 1][i + 1]) + A[j][i]; } else if (i == n - 1) { s[j][i] = Math.min(s[j - 1][i], s[j - 1][i -1]) + A[j][i]; } else { s[j][i] = A[j][i] + Math.min( Math.min(s[j - 1][i], s[j - 1][i + 1]), s[j - 1][i - 1]); } } } int res = s[n - 1][0]; for (int i = 1; i < n; i++) { if (s[n - 1][i] < res) { res = s[n - 1][i]; } } return res; } }
Сложность этого алгоритма в O(n²)
во времени и пространстве. Примечание: мы могли бы улучшить пространственную сложность, поскольку мы используем только предыдущую строку для вычисления следующей. Поэтому сложность пространства может быть O(n)
.
Удачного кодирования!
Что дальше:
- Ознакомиться с решением другой задачи: Минимальный поворот доминошки для равного ряда
- Свяжитесь со мной: [email protected]
- Хотите пройти собеседование на должность инженера-программиста? Свяжитесь со мной :)