递归 Fib 风格函数变成迭代函数？

Question

我在java中有一个函数，它是用递归算法编写的，需要以迭代形式编写。问题是我不知道从哪里开始思考新的算法。这是我正在做的一项作业。

考虑以下计算问题：

假设您是一名顾问，并且您有一系列 n 个潜在的咨询工作，其报酬为 A[0],A[1],..,A[n -1] 美元（因此工作 0 支付 A[0] 美元，工作 1 支付 A[ 1] 美元等）。

此外，作业 i 于 i (i = 0 ; : : : ; n 1 ) 天开始。

但是，每个工作需要 2 天，因此您不能连续执行两个工作。目标是确定最大金额，用 F(n) 表示；您可以从 n 个职位 A[0] 到 A[n-1] 中选择的有效工作计划中赚取收入 : 例如，考虑以下输入数组：

  0 1 2 3 4 5
A 5 6 8 6 2 4

最佳计划是执行作业 0 ； 2 ; 和 5 ;金额 赚取，F(6) = A[0] + A [2] + A [5] = 17 ；尽可能大。请注意，这 是一个有效的计划，因为不包含两个连续的作业。

解决这个问题的递归版本的函数如下：

public static int jobScheduleRecursive(int[] A, int n) 
{
    n = A.length;
    if(n == 0){return 0;}
    else if(n == 1){return A[0];}
    else if(n >= 2){return max(jobScheduleRecursive(A, (n-1)), (A[n-1]) 
                           + jobScheduleRecursive(A, n-2));}
    else return -1;
}

总之，我必须想出一个迭代算法来完成这项工作。唯一的问题是我不知道如何继续。如果有任何建议能够引导我走向正确的方向，我将不胜感激。

Answer 1

有时，已知问题的递归解决方案的迭代解决方案并不像递归解决方案那样直接。实现迭代解决方案的最简单方法是使用 - 动态编程 基本上你想要的是创建一个临时数组，保存途中所有子问题的解决方案。为此，请根据输入的大小创建一个动态分配的数组。例如，如果您的递归函数是 int foo(int a)
用 1..n 的解决方案填充数组，其中 n 是原始问题的输入。
更改算法，它不再递归地调用自身，而是检查数组中是否存在子问题的解决方案，如果不存在，则将其填充。这样子问题就不会计算次数，而只会计算一次。