求助一道算法题，求最便宜路径

[kidding]

问题如下

你正在玩一款游戏。一共有 n 个镇，现在你在 a 镇并想走到 b 镇。与其他游戏中可以不停地走上几个小时不同，在这个游戏里你不能这样做。你有当前的耐力点数，如果耐力降至 0，则将无法再走下去。

在相距 d 公里的两个城镇之间的道路上行走会消耗 d 耐力点。如果你目前没有至少 d 耐力点，那么你将不能走这条路。

每个城镇都有一个旅馆可以休息。每休息一小时，就会恢复 1 点耐力，直至你的最大耐力点 m 。每家旅馆都有不同的每个小时休息价格。

你不想在旅馆里浪费不必要的钱。请问从起始城镇 a 到目的地城镇 b 最便宜的价格是多少？

本来以为是最短路径问题，但想了一下如果当前体力不够完全可以绕路去附近比较近的城市休息才可以保证总价格最便宜。甚至有可能附近的城市是死路，但可以过去恢复完耐力再往回走，所以也不能简单地把每个城市的旅馆价格作为权重。

想了很久也没想出解法，所以发出来问问大家意见。

[litmxs]

动态规划吧，记 dp[i]为从 a 镇到 i 镇最便宜的价格，dp[a]=0，参考 Dijkstra 算法更新 dp 数组

[kidding]

@litmxs #1 感谢回复。应该是个 DP 问题，但只算最便宜价格的话没法考虑耐力恢复的问题吧。

[litmxs]

@kidding 应该再加一个维度，dp[i][j]表示到达城镇 i，耐力至少剩余 j 最便宜的价格

[kidding]

@litmxs #3 刚才尝试写了一下，但增加维度的话在 dijkstra 算法比较价格的时候又不太好比较了，因为多了一个维度并且长度是最大体力值。难道说我应该在比较的时候枚举每个可能的体力值来更新这个数组吗？

[GuuJiang]

dp(i, k)表示到达第 i 个镇并且剩余 n 点耐力所需的最小花费
d[i][j]表示第 i 个镇和第 j 个镇之间的距离
cost[i]表示第 i 个镇恢复一点耐力所需的价格
dp(i, k) = min(dp(j, k-c+d[i][j]) + cost[i] * c for j in [0..n] for c in [0..m])
dp(0, k) = cost[0] * k
使用记忆化搜索求出 dp(n-1, 0)即可