leetcode：5270. 网格中的最小路径代价【简单层次dp】

分析

从第一层开始
求初每一层的每个节点最小花费
比如说我要求这层的某个节点，就要看上层的值dp加上值再加上边权的最小值即可
注意我这里每层的dp不计入当前层的值
所以最后一层dp算完还要加上最后一层的值
要理解好题意

ac code

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [0] * n
        for i in range(1, m):
            ndp = [inf] * n
            for j in range(n):
                for k in range(n):
                    pre = grid[i - 1][k]
                    ndp[j] = min(ndp[j], dp[k] + pre + moveCost[pre][j])
            dp = ndp
            #print(dp)
        
        for j in range(n):
            dp[j] += grid[-1][j]
        #print(dp)
        
        return min(dp)
            

总结

每层贪心求最短
dp只与上一层有关系