1289.Minimum Falling Path Sum II

tags: Hard,Array,DP,Matrix

1289. Minimum Falling Path Sum II

題目描述

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

範例

Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2:

Input: grid = [[7]]
Output: 7

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99

解答

Javascript

$O(n^3)$

function minFallingPathSum(grid) {
  if (grid.length === 1) return grid[0][0];
  for (let i = 1; i < grid.length; i++) {
    for (let j = 0; j < grid.length; j++) {
      grid[i][j] += Math.min(...grid[i - 1].filter((_, index) => index !== j));
    }
  }

  return Math.min(...grid[grid.length - 1]);
}

吉神：都Hard了就是不要你寫

$O(n^3)$
Marsgoat Dec 13, 2022

$O(n^2)$

function minFallingPathSum(grid) {
  if (grid.length === 1) return grid[0][0];
  for (let i = 1; i < grid.length; i++) {
    let min = Infinity;
    let secondMin = Infinity;
    let index = 0;
    // 找出上一行的最小跟第二小的值
    for (let j = 0; j < grid.length; j++) {
      if (grid[i - 1][j] < min) {
        secondMin = min;
        min = grid[i - 1][j];
        index = j;
      } else if (grid[i - 1][j] < secondMin) {
        secondMin = grid[i - 1][j];
      }
    }

    // 更新 grid[i][j]
    for (let j = 0; j < grid.length; j++) {
      if (j === index) {
        grid[i][j] += secondMin;
      } else {
        grid[i][j] += min;
      }
    }
  }

  return Math.min(...grid[grid.length - 1]);
}

更新版本，跟吉神學習了，本來醜到爆的版本放到Discord給大家笑。
Marsgoat Dec 16, 2022

C++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 1) return grid[0][0];
        for (int i = 1; i < n; i++) {
            int m1 = INT_MAX, idx = -1, m2;
            for (int j = 0 ; j < n; j++) {
                int value = grid[i-1][j];
                if (value <= m1) {
                    m2 = m1;
                    m1 = value;
                    idx = j;
                } else if (value < m2) {
                    m2 = value;
                }
            }
            for (int j = 0; j < n; j++) {
                grid[i][j] += j == idx? m2 : m1;
            }
        }
        return *min_element(grid[n-1].begin(), grid[n-1].end());
    }
};

Yen-Chi ChenTue, Dec 13, 2022

Python

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1: return grid[0][0]
        for i in range(1, n):
            m1, idx = math.inf, -1
            for j in range(n):
                value = grid[i-1][j]
                if value <= m1:
                    m2 = m1
                    m1 = value
                    idx = j
                elif value < m2:
                    m2 = value
            for j in range(n):
                grid[i][j] += m1 if idx != j else m2
        return min(grid[-1])

Yen-Chi ChenTue, Dec 13, 2022

Reference

回到題目列表