我有一个递归关系，它是这样的：
E(i，j)=A[i]+A[j]+E(i+1，j-1)+E(i+2，j)+E(i，j-2)；如果i！=j
E(i，j)=A[i]；如果(i＝＝j)
E(i，j)＝0；如果i<0或j<0
A[i]1<=i<=N是简单的整数数组。
我想在时间复杂度上求解E(1，N)比求解O(N^2)更好。我想知道我们是否可以为这种递推找到一些闭合形式的公式，或者也许是一种计算E(1，N)值的聪明方法？
欢迎任何提示，
提前感谢。
编辑：
实际问题如下：
- 我们有一个数组A[]，2名玩家轮流玩这个游戏
- 玩家可以选择概率为0.5的最左边或最右边的数字，并将其添加到自己的分数中(如果数组中只剩下一个元素，他只需选择该数字，游戏结束)
- 问题是找到Player1将达到的预期分数
关于您的复发关系：
这似乎有点困难，因为总结表明，对于E(1，N)，我们需要E(2，..)和E(3，..)，每一个都需要具有更高"i"等的其他条目。
现在，重新排列术语，这样我们就可以孤立具有最高"i"的E术语(一般来说，递归关系的一个好主意是查看不同的排列来孤立特定的索引-最高、最低、中间的索引，…)：
E(i+2，j)=E(i，j)-E(i，j-2)-E(i+1，j-1)-A(i)-A(j)
然后，将所有i下移2(简单地重写公式)
E(i，j)=E(i-2，j)-E(i-2、j-2)-E(i-1、j-1)-A(i-2)-A(j)。
然后，对于{i=1，j=N}，这就是您正在寻找的，我们得到：
E(1，N)=E(-1，N)-E(-1，N-2)-E(0，N-1)-A(-1)-A(N)=-A(N。
(当然，我假设，对于I＝0/j＝0，E(I，j)和A(I)为零；当您只为负索引而不是为零索引指定零值时，您的规范可能是不完整的)。
然后，关于你对基本情况的(编辑过的)描述——两个玩家从A开始轮流，从左到右任意，直到A耗尽：
从之前的结果来看，我不认为你的递归关系描述了潜在的游戏，考虑到结果——A(N)。。。因此，把递归关系放在一边(对于i=1，它无论如何都是求解的)。看看游戏本身，我们可能会得到什么关系。
[编辑后继续]
到目前为止，我还没有想出一些可以以封闭形式投射的东西，即比处理某种递归关系更快的东西。因此，就目前而言，让我们写下如何以一种适合计算的方式描述游戏。
定义以下数量：
设X(i，k)是项目#i(在阵列A中)在回合#k结束时仍然存在(即尚未被任何玩家占据)的概率(对来自两个玩家的回合进行计数)。当然，k在我们的游戏中从1到N运行，i也是。为了验证目的，我们可以注意到，对于所有i，X(i，N)必须为零：在游戏结束时，所有元素都已被取下。
如果我们可能需要(在公式评估中)任何超出"正常"范围的X(i，k)值，我们评估：
X(i,k)=1 for {1<=i<=N; k=0}: initially all elements in A are still there.
X(i,k)=0 whenever i<1 or i>N: no elements ever exist outside the (original) range of A.
接下来，设T(i，k)是元素#i在第#k回合被(任何玩家)准确地占据的概率。这必须是0.5*它是最左边的元素(当前)的概率，这相当于说元素#(i-1)不存在于前一个转弯的末端，加上0.5*它(当前)是最右边的元素的概率，而这又相当于说单元#(i+1)不存在在前一个转向的末端，而所有这些必须乘以元素#i本身首先存在的概率：
T(i,k) = X(i,k-1) * ( (1-X(i-1,k-1)) + (1-X(i+1,k-1)) ) / 2
元素#i在第#k个转弯后仍然存在的概率X(i，k)是它在前一个转弯结束时存在的概率，减去它在第#k:转弯时被占用的概率
X(i,k) = X(i,k-1) - T(i,k)
元素#i与玩家#1一起结束的概率是T(i，k)的所有回合k的总和，但仅计算HIS回合。让我们用P(i，1)来表示这个数量，其中1代表玩家#1。
P(i,1) = sum{ k=1,3,...: T(i,k) }
同样，对于玩家#2：
P(i,2) = sum{ k=2,4,...: T(i,k) }
玩家#1的预期得分是总和S(1):
S(1) = sum( i=1..N: P(i,1)*A(i) }, and likewise for player #2: S(2) = sum( i=1..N: P(i,2)*A(i) }
从上面的公式来看，我看不出有什么方法可以避免关于时间的O(N2)方法。内存使用率可能是O(N)，因为我们可能会继续运行总计并丢弃不再需要的旧"元素"数据。考虑到这一点——假设你没有处理过长的数组A——玩家将无法生存！-O(n2)时间性能在实践中不应该是这样的问题。
int N = sizeof(A);
// note on the code below: we'll use i as an integer running over the elements in A, and k running over the turns that players make.
// while in human parlance we would have them (both) run from 1 to N, the zero-based arrays of C++ make it more convenient to let them
// run from 0 to N-1.
// initialize the running totals P(i), the accumulated (over turns) probabilities that element #i winds up with player #1.
// if we ever need the same for player #2, it's values are of course 1-P (that is: at the end of the game).
double* P = new double[N];
for (int i=0; i<N; i++)
{
P[i] = 0; // before we start, there's little chance that player #1 has already taken any element.
}
// initialize the existence-array for the elements.
int* X = new int[N];
for (int i=0; i<N; i++)
{
X[i] = 1; // initially all elements exist, i.e. have not yet been taken by any player.
}
// declare an array for processing the probabilities that elements are taken at a particular turn.
double* T = new double[N];
// iterate over the turns.
for (int k=0; k<N; k++)
{
// for each element, calculate the probability that it is taken NOW.
// the current values of X - the existence array - refer to the (end of the) previous turn.
for (int i=0; i<N; i++)
{
// note: take care of the boundaries i=0 and i=N-1.
if (i == 0)
{
T[i] = X[i] * ( 2 - X[i+1] ) / 2;
}
else if (i == N-1)
{
T[i] = X[i] * ( 2 - X[i-1] ) / 2;
}
else
{
T[i] = X[i] * ( 2 - X[i-1] - X[i+1] ) / 2;
}
} // element i
// with the take-probabilities for this turn in place, update P - only at odd turns (i.e. k=even): P is for player #1 only.
if (k % 2 == 0)
{
for (int i=0; i<N; i++)
{
P[i] += T[i];
}
}
// finally - in this turn - update the existence array.
for (int i=0; i<N; i++)
{
X[i] -= T[i];
}
} // turn k
// result: calculate the expected score for player #1.
double score = 0;
for (int i=0; i<N; i++)
{
score += P[i] * A[i];
}
--
由于概率相等，这只是一个计数问题。
你能算出在第k个转弯时选择A[j]的几率吗？