LeetCode 1289. Descent path min and II

Title address (1289. The descent path is the smallest and II)

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

Title Description

Here's an integer matrix  arr , Definition 「 Nonzero offset descent path 」 by ： from  arr Select a number for each row in the array , And in the numbers selected in order , Adjacent numbers are not in the same column of the original array .

Please return the minimum value of the sum of the number of nonzero offset descent paths .

 Example  1：

 Input ：arr = [[1,2,3],[4,5,6],[7,8,9]]
 Output ：13
 explain ：
 All nonzero offset descent paths include ：
[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 path of the smallest number and number is the descent  [1,5,7] , So the answer is  13 .

Tips ：

1 <= arr.length == arri.length <= 200

-99 <= arri <= 99

Ideas

use DP planning , Calculation of different columns min

Code

• Language support ：Python3

Python3 Code:

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        length = len(grid)
        #  structure DP Matrix for recording 
        dp =  [[0]*length for i in range(length)]
        dp[0] = grid[0]
        for i in range(1,length):
            lastList = dp[i - 1]
            for j in range(length):
                val = 0
                # print(j,lastList[:j],lastList[j+1:])
                # ## Set the particularity of boundary conditions 
                if j == 0:
                    val = min(lastList[j+1:])
                elif j == length-1:
                    val = min(lastList[:j])
                else:# Calculate the minimum value of the left and right arrays of the previous layer 
                    val = min(min(lastList[:j]),min(lastList[j+1:]))
                # Add this value after calculating the minimum value 
                dp[i][j] = val + grid[i][j]
        # print(dp)
        return min(dp[-1])

if __name__ == '__main__':
    arr = [[1,2,3],[4,5,6],[7,8,9]]
    res = Solution().minFallingPathSum(arr)
    print(res)

Complexity analysis

Make n Is array length .

• Time complexity ：$O(n^2)$
• Spatial complexity ：$O(n^2)$