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

本文主要是介绍931. 下降路径最小和-Python-DP-简单题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 931. 下降路径最小和

思路

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

解题方法

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

复杂度

时间复杂度:$O(n\ast n)$

空间复杂度:$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])

这篇关于931. 下降路径最小和-Python-DP-简单题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---