c - 如何在以下递归中实现动态规划？

Question

我有以下递归:

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。

Answer 1

这闻起来很像家庭作业问题。我建议你与讲师或助教见面，因为这是最好的互动学习方式。如果您使用此信息，请确保引用它，以免发生剽窃。

首先，观察结果在值 [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 的每个组合的系数和一个 bool 值。自 N上限为 2000，这意味着您只需要 4000 个条目，这不应该是太大的负担。事实上，您可以放弃递归并像我们上面那样简单地增量计算整个表。