双递归动态编程

Question

我是动态编程的新手。我不能理解下面的双重递归。有人能解释一下是如何工作的吗

int N; // read-only number of wines in the beginning
int p[N]; // read-only array of wine prices
int profit(int be, int en) {
if (be > en)
return 0;
// (en-be+1) is the number of unsold wines
int year = N - (en-be+1) + 1; // as in the description above
return max(
profit(be+1, en) + year * p[be],
profit(be, en-1) + year * p[en]);
}

Answer 1

将be和en视为积分闭区间[be; en]的边界。在每次递归中，您从任意一个绑定中删除一个元素，直到间隔变为空。

随着每次新的迭代，en-be的值将减小，因此year将增加。

实际计算的是(be0和en0是起始值，即对函数的第一个非递归调用的值)：

en0
Σ     ((N-en0) + i) * p[S(i)])
i = be0

其中S(x)是一些(理论上的)选择器函数[be0; en0] -> [be0, en0]，其取决于递归期间计算的最大值。

这个选择器函数必然是双射的(即，每个p[x]在[be0；en0]中的x的和中只出现一次)：

max
(
profit(be + 1, en) + year * p[be],
profit(be, en - 1) + year * p[en]
);

随着每次递归的返回，您将添加一个不在递归期间考虑的间隔中的索引值。由于S是双射的，它将产生[be0；en0]的置换P；然而，它不能产生任意的排列；每个子区间总是是两种形式之一：

[beR, P(beR + 1, ..., enR)]
[P(beR, ..., enR - 1), enR]

但CCD_ 10和CCD_。

回到葡萄酒图像：你按照p中定义的顺序对葡萄酒进行排序，每年，你总是删除这一行的开头或结尾，但永远不要选择在中间的一个。

不过，到目前为止，还没有涉及动态编程。

如果你仔细观察你的递归，你会发现你有重叠的子问题：

profit(be, en)
profit(be + 1, en)
profit(be + 2, en)
profit(be + 1, en - 1)    <---
profit(be, en - 1)
profit(be + 1, en + 1)    <---
profit(be, en - 1)

i。e.你在同一时间段内做同样的工作不止一次。要引入动态编程，您需要最小限度地扩展您的算法：

int profit(int be, int en)
{
if (be > en)
return 0;
int solution;
if(getSolution(be, en, solution))
return solution;
int year = ...;
solution = std::max(...); // recursive calls
addSolution(be, en, solution);
return solution;
}

其中适当的实现方式取代CCD_ 13和CCD_。