动态规划算法与递推关系
Dynamic programming algorithm and recurrence relation
有谁知道如何回答这个问题？我被困了几天想弄明白。
一位学生决定骑自行车从温哥华到哈利法克斯。
她从 0 公里处开始在路上。沿途有 n 家旅馆 H1，。 . . ，嗯，在
距离 h_1 < h_2 < h_3 < . . . < h_n−1 < h_n 分别距离旅行的起点。
学生愿意过夜的地方只有这些旅馆，但她
可以选择她停留的酒店。她必须在最后一家酒店 H_n 停留，因为这是她的
目的地（她计划飞回去）。
理想情况下，该学生希望每天行驶 100 公里，但这可能是不可能的，
取决于酒店的间距。为了确定学生有多接近
对于这个目标距离，她将一天的惩罚定义为 |100 − x|^1.5，其中 x 是
那天走过的距离。她 objective 计划她的旅行时尽量减少
旅行所有天数的每日罚款总和。
- 写出 D_k 的递归关系，其中 D_k 是在酒店 H_k 结束的所有可能行程中每日罚金的最小总和（即，学生不再继续)
- 找到计算 D_n 的动态规划算法。
我认为思考这个问题的最好方法是向后思考。比方说你在酒店 N，最后一个最优的最后一个是什么？是n-1吗？ n-2？ n-3？然后，您选择最好的并向后工作，直到到达起点
F(n) = min( F(j) + abs(100 - h_n + h_j)^1.5 ) where 0 < j < n
有谁知道如何回答这个问题？我被困了几天想弄明白。
一位学生决定骑自行车从温哥华到哈利法克斯。 她从 0 公里处开始在路上。沿途有 n 家旅馆 H1，。 . . ，嗯，在 距离 h_1 < h_2 < h_3 < . . . < h_n−1 < h_n 分别距离旅行的起点。 学生愿意过夜的地方只有这些旅馆，但她 可以选择她停留的酒店。她必须在最后一家酒店 H_n 停留，因为这是她的 目的地（她计划飞回去）。 理想情况下，该学生希望每天行驶 100 公里，但这可能是不可能的， 取决于酒店的间距。为了确定学生有多接近 对于这个目标距离，她将一天的惩罚定义为 |100 − x|^1.5，其中 x 是 那天走过的距离。她 objective 计划她的旅行时尽量减少 旅行所有天数的每日罚款总和。
- 写出 D_k 的递归关系，其中 D_k 是在酒店 H_k 结束的所有可能行程中每日罚金的最小总和（即，学生不再继续)
- 找到计算 D_n 的动态规划算法。
我认为思考这个问题的最好方法是向后思考。比方说你在酒店 N，最后一个最优的最后一个是什么？是n-1吗？ n-2？ n-3？然后，您选择最好的并向后工作，直到到达起点
F(n) = min( F(j) + abs(100 - h_n + h_j)^1.5 ) where 0 < j < n