我有以下递归：
if(a%2 == 0){
f([a1,a2,...,aN],a,N) = (a1 + aN)/2 + f([a1,a2,...,a(N-1)],a+1,N-1)/2 +
f([a2,...,aN],a+1,N-1)/2;
}
else{
f([a1,a2,...,aN],a,N) = f([a1,a2,...,a(N-1)],a+1,N-1)/2 +
f([a2,...,aN],a+1,N-1)/2;
}
基本情况：
f([a1,a2],a,2) = (a1+a2)/2;
显然，如果我递归地实现它，就会出现堆栈溢出。我应该如何利用动态规划来获得这个递归的最优解？
[a1,a2,..,aN] 表示一个整数数组。
N 的限制是 2000 并且 a1,a2,..,aN <=999。
这闻起来很像家庭作业问题。我建议您与讲师或助教见面，因为这是最好的互动学习方式。如果您使用此信息，请务必引用它，以免抄袭。
首先，观察结果在值中是线性的[a0, a1, ... aN]。因此，您实际上只需要跟踪它们的系数。出于符号的目的，让我们写{b1, b2, ..., bN}来表示b1 * a1 + b2 * a2 + ... bN * aN。
接下来，手动计算一些递归：
f([a1, a2], a, 2) = { 1/2, 1/2 }是 的基本情况N=2。
让我们看看N=3：
f([a1, a2, a3], a, 3)对于a偶数 = {1/2, 0, 1/2} + { f([a1, a2], a+1, 2)/2, 0 } + { 0, f([a2, a3], a+1, 2)/2 } = { 1/2, 0, 1/2 } + { 1/4, 1/4, 0 } + { 0, 1/4, 1/4 } = { 3/4, 1/2, 3/4 }。
f([a1, a2, a3], a, 3)对于a奇数 = { f([a1, a2], a+1, 2)/2, 0 } + { 0, f([a2, a3], a+1, 2)/2 } = { 1/2, 0, 1/2 } + { 1/4, 1/4, 0 } + { 0, 1/4, 1/4 } = { 1/4, 1/2, 1/4 }。
现在N=4：
f([a1, a2, a3, a4], a, 4)对于a偶数 = { 1/2, 0, 0, 1/2 } + { f[a1, a2, a3], a+1, 3)/2, 0 } + { 0, f([a2, a3, a4], a+1, 3)/2 }。因为a是a+1偶数，所以是奇数，所以我们在这种情况下F([], even, 3)。f([a1, a2, a3, a4], a, 4)对于a偶数 = { 1/2, 0, 0, 1/2 } + { 1/8, 1/4, 1/8, 0 } + { 0, 1/8, 1/4, 1/8 } = { 5/8, 3/8, 3/8, 5/8 }。
f([a1, a2, a3, a4], a, 4)对于a奇数 = { f[a1, a2, a3], even, 3)/2, 0 } + { 0, f([a2, a3, a4], even, 3)/2 } = { 3/8, 1/4, 3/8, 0 } + { 0, 3/8, 1/4, 3/8 } = { 3/8, 5/8, 5/8, 3/8 }。
现在您可以看到系数仅取决于N偶数a或奇数。
这意味着您的动态编程只需要记住每个组合的系数N和一个布尔值。由于N上限为 2000，这意味着您只需要 4000 个条目，这不应该是太大的负担。事实上，您可以放弃递归并像我们上面所做的那样简单地增量计算整个表。
您需要存储所有 a,N 值对的答案
可以以增量方式计算每个 ai 的系数。我相信给定 n 的一半系数需要计算，因为另一半将包含重复的元素。所以每个 n 将在表中包含 n/2 个值。这种方法将导致 n^2 运行时间。不知道这可以进一步改进。