完整的问题陈述是 here 。假设我们有一个已知值的双端队列。每一轮，我们都可以从一端或另一端取出一个值，并且仍在队列中的值增加为 value*turns 。目标是找到最大可能的总值(value)。
我的first approach是使用简单的自上而下的 DP 和内存。让i , j表示值数组 A[] 的“子数组”的起始、结束索引.
A[i]*age if i == j
f(i,j,age) =
max(f(i+1,j,age+1) + A[i]*age , f(i,j-1,age+1) + A[j]*age)
然而，事实证明这种方法太慢了，因为存在多余的堆栈调用。自下而上的迭代应该更快。
让m[i][j]是 A[] 的“子数组”的最大可达值带有开始/结束索引 i , j 。因为i <= j ，我们只关心下三角部分。
可以使用 m[i][j] = max(m[i-1][j] + A[i]*age, m[i][j-1] + A[j]*age) 迭代构建该矩阵，其中age对角线上最大(大小为 A[] 并线性减小为 A.size()-(i-j) 。
我的尝试implementation与 bus error 会面.
所描述的算法正确吗？总线错误的原因是什么？
这是代码中唯一可能发生总线错误的部分:
for(T j = 0; j < num_of_treats; j++) {
max_profit[j][j] = treats[j]*num_of_treats;
for(T i = j+1; i < num_of_treats; i++)
max_profit[i][j] = max( max_profit[i-1][j] + treats[i]*(num_of_treats-i+j),
max_profit[i][j-1] + treats[j]*(num_of_treats-i+j));
}
最佳答案
for(T j = 0; j < num_of_treats; j++) {
在此循环内，j显然是数组 max_profit 的有效索引。但您不仅仅使用 j .
关于c++ - 给奶牛的款待——自下而上的动态规划，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25612429/