每日一题|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

 

原文地址：https://blog.csdn.net/m0_57527624/article/details/142693667

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！