如何在动态规划中做出正确的函数

Question

我在动态规划中遇到以下问题

一个人有时间机器，他可以在 1 年或 2 年的时间里移动。一开始他在 0 年，他想到达 100 年。他做的每一步（1 年或 2 年）都是支付一些固定费用。有一个100个整数的数组代表他去投了特定年份需要支付的费用。

我需要使用动态规划找出这个人从第 0 年到第 100 年可以支付的最低金额。

根据我目前所做的，我认为应该有类似

的内容

minCost(i) = min{A[i-1], A[i-2]}

基本情况是第 1 年和第 2 年，分别花费 A[1]、A[2]。但我认为这种方法更多的是贪婪算法而不是动态规划。

看到了动态规划的装箱算法，理解了它和表示它的矩阵

上面显示的问题的矩阵应该是什么样的？

我应该如何构建这个问题的函数和伪代码？

Answer 1

你快到了。

想一想，从第i-1年到第i-2年，你将如何走到第i年。您忘记考虑一项费用。

MinCostToReachYear(i) = min( MinCostToReachYear(i-1) + fee(i-1), MinCostToReachYear(i-2) + fee(i-2) )

您已经知道第 1 年和第 2 年的基本情况。您能否考虑使用 for 循环进行外推，或者使用上面提到的您已经知道的递归函数更轻松地进行外推？我把它留给你作为练习。