當前位置:網站首頁>模擬卷Leetcode【普通】931. 下降路徑最小和

模擬卷Leetcode【普通】931. 下降路徑最小和

2022-05-14 07:22:03邂逅模擬卷

931. 下降路徑最小和

給你一個 n x n 的 方形 整數數組 matrix ,請你找出並返回通過 matrix 的下降路徑 的 最小和 。

下降路徑 可以從第一行中的任何元素開始,並從每一行中選擇一個元素。在下一行選擇的元素和當前行所選元素最多相隔一列(即比特於正下方或者沿對角線向左或者向右的第一個元素)。具體來說,比特置 (row, col) 的下一個元素應當是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1:

輸入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
輸出:13
解釋:下面是兩條和最小的下降路徑,用加粗+斜體標注:
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]
示例 2:

輸入:matrix = [[-19,57],[-40,-5]]
輸出:-59
解釋:下面是一條和最小的下降路徑,用加粗+斜體標注:
[[-19,57],
[-40,-5]]
示例 3:

輸入:matrix = [[-48]]
輸出:-48

提示:

n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/minimum-falling-path-sum
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

代碼:

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        """ 典型的動態規劃,記錄到每一行最小值,計算每一行的時候看上一行的左中右哪個最小 """
        pass

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        length = len(matrix)
        min_lastline = matrix[0]
        for line in matrix[1:]:
            min_thisline = [0]*length
            for colid,num in enumerate(line):
                min_thisline[colid] = num + min(min_lastline[max(0,colid-1):min(length,colid+2)])
            min_lastline = min_thisline
        return min(min_lastline)


def test(data_test):
    s = Solution()
    return s.minFallingPathSum(*data_test)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [[[2,1,3],[6,5,4],[7,8,9]]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

備注:
GitHub:https://github.com/monijuan/leetcode_python

CSDN匯總:模擬卷Leetcode 題解匯總_卷子的博客-CSDN博客

可以加QQ群交流:1092754609

leetcode_python.utils詳見匯總頁說明
先刷的題,之後用脚本生成的blog,如果有錯請留言,我看到了會修改的!謝謝!

版權聲明
本文為[邂逅模擬卷]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205140610223275.html

隨機推薦