动态规划中如何实现正确的函数

Question

我在动态规划中有以下问题。

一个人有时间机器，他可以在1年或2年内及时移动。在开始的时候，他是0岁，他想达到100岁。他做的每一步(1到2年)都要支付一些固定的费用。有一个包含100个整数的数组，表示如果他投出了特定年份，他需要支付的费用。

我需要找到一个人可以支付的最低数额，从0到100，使用动态规划。

从我到目前为止所做的事情来看，我认为应该有这样的事情

minCost(i) = min{Ai-1，Ai-2}

基例分别为年份1和2，费用分别为A1、A2。但我认为这种方法更多的是贪婪算法，而不是动态规划。

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

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

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

Answer 1

你快到了。

想想你将如何从第一年和第二年到达第一年.有一笔费用你忘了考虑。

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

你已经知道了第一年和第二年的基本情况。你能想到用一个for循环来推断，还是像上面提到的那样更容易地使用递归函数来推断呢？我把它留给你做练习。