每日一题|1928. 规定时间内到达终点的最小花费|动态规划、最小路径

本题需要使用动态规划进行解决。

分析： 求解最小值而且每一次的状态是由上一次的状态推导出来的，用动态规划。

难点：dp数组的定义和更新。

1、dp数组的定义

在时刻t，位置i处，此时的花费可以表示为如下的形式：

 注意到道路是双向的，也就是i和j可以互换位置，所以在后面遍历的时候需要更新两个值。

2、确定更新公式

一次迭代中双向道路更新两个值：

dp[t][i] = min(dp[t][i], dp[t - cost][j] + passFees[i]) -- 从j 到i 需要交i 过路费

dp[t][j] = min(dp[t][j], dp[t - cost][i] + passFees[j]) -- 从i 到j 需要交j 过路费

3、初始化

dp是一个二维数组，col数量是len(passFees)，row数量是maxTime + 1（因为t能够达到maxTime）。

更新dp使用min函数，所以初始化dp全部是float('inf')，然后把dp[0][0] = passFees[0]。

4、更新顺序

外层循环遍历t，从1开始到maxTime + 1；

内层循环遍历节点，也就是每一个edge解包出来的节点和时间开销；注意需要两次更新。

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        n = len(passingFees)
        dp = [[float('inf')] * n for _ in range(maxTime + 1)]

        dp[0][0] = passingFees[0]

        for t in range(1, maxTime + 1):
            for i, j, cost in edges:
                if cost <= t:
                    dp[t][i] = min(dp[t][i], dp[t - cost][j] + passingFees[i])
                    dp[t][j] = min(dp[t][j], dp[t - cost][i] + passingFees[j])
        
        ans = min(dp[t][n-1] for t in range(1, maxTime + 1))
        return -1 if ans == float('inf') else ans