最小路径和
题目链接: https://leetcode.cn/problems/minimum-path-sum/
解题思路:
设定dp[i][j],代表自顶至下到[i][j]位置最小路径和
dp[0][0]=grid[0][0]
由说明可知,每次只能向下或者向右移动一步,得状态转移方程为dp[i][j]=min(dp[i-1][j],dp[i][j-1])+v[i][j]
dp[i][0]和dp[0][j]需要特殊处理
dp[i][0]=dp[i-1][0]+v[i][j]
dp[0][j]=dp[0][i-1]+v[i][j]
提示中告诉我们n,m>0
复杂度分析
时间复杂度: 时间复杂度是 ,其中 是数组
grid
的长度空间复杂度: 空间复杂度是 ,我们需要一个n*n二维数组存储每个位置的状态。
最后更新于