В этой задаче на Литкоде нам нужно вычислить стоимость минимального пути, учитывая следующую задачу:

Учитывая квадратный массив целых чисел A, нам нужна минимальная сумма падающего пути через A.

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

Эта проблема обычно относится к тому типу проблем, которые решаются с помощью динамического программирования. Если вы не знаете, что такое динамическое программирование, не проблема, мы пройдем его вместе. Причина, по которой вы можете догадаться, что это решаемо с помощью динамического программирования, заключается в том, что:

  1. Количество путей экспоненциально зависит от количества строк (размер задачи)
  2. Существует простое рекуррентное соотношение между стоимостью доступа к «соседним» пространствам, позволяющее легко вычислить стоимость минимальных путей для строки, учитывая стоимость минимальных путей из предыдущей строки.

На примере, предоставленном вместе с задачей, покажем, как работает алгоритм:

Шаг 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).

Удачного кодирования!

Что дальше: