931. 下降路径最小和-Python-DP-简单题

2024-01-07 23:08:14

Problem: 931. 下降路径最小和

思路

看了一些题解,感觉写的很复杂,其实我的思考很简单,直接在原数组进行修改

解题方法

第一行不变,从第二行开始,能到达当前位置的路径最多只有三条(在边界时只有两条),随后逐层赋值,最后返回最后一层的最小值就是结果,hhh是不是非常easy

复杂度

时间复杂度: O ( n ? n ) O(n*n) O(n?n)

空间复杂度: O ( 1 ) O(1) O(1)

Code

class Solution:
    def minFallingPathSum(self, dp: List[List[int]]) -> int:
        n=len(dp)
        for i in range(1,n):
            for j in range(n):
                if j ==0:
                    dp[i][j]+=min(dp[i-1][j],dp[i-1][j+1])
                elif j==n-1:
                    dp[i][j]+=min(dp[i-1][j],dp[i-1][j-1])
                else:
                    dp[i][j]+=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])
        return min(dp[-1])

文章来源:https://blog.csdn.net/weixin_53415043/article/details/135390959
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。