931. Minimum Falling Path Sum

https://leetcode.com/problems/minimum-falling-path-sum/

Python

Buttom-Up DP (DP Table)

• Time: O(M*N)
• Space: O(M*N)

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])

        dp = [[0]*n for i in range(m)]
        dp[0] = matrix[0]

        for row in range(1, m):
            for col in range(n):
                parent_min = dp[row-1][col]
                if col-1 >= 0:
                    parent_min = min(parent_min, dp[row-1][col-1])
                if col+1 < n:
                    parent_min = min(parent_min, dp[row-1][col+1])

                dp[row][col] = parent_min + matrix[row][col]

        return min(dp[-1])

Javascript

var minFallingPathSum = function(matrix) {
    let dp = [];
    for (let row = 0; row < matrix.length; row++) {
      let tmp = [];

      for (let col = 0; col < matrix[0].length; col++) {
        if (row === 0) {
          tmp[col] = matrix[row][col];
        } else {
          const left = dp[col - 1] !== undefined ? dp[col - 1] + matrix[row][col] : Infinity;
          const mid = dp[col] + matrix[row][col];
          const right = dp[col + 1] !== undefined ? dp[col + 1] + matrix[row][col] : Infinity;

          tmp[col] = Math.min(left, mid, right);
        }
      }
      dp = tmp;
    }

    return Math.min.apply(null, dp)
};