最小路径和
题目链接: 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
复杂度分析
最后更新于