苹果格

Question

我在一个编程论坛上发现了这个问题：

一个由N*M细胞组成的表，每个细胞都有一定数量的苹果。你从左上角开始。在每一步中，您都可以向下或向右移动一个cell.Design算法，如果您从左上角移动到右下角，则查找可以收集的最大苹果数。。

我想过三种不同的肤色--时间和空间

方法1最快：

for(j=1,i=0;j<column;j++)
    apple[i][j]=apple[i][j-1]+apple[i][j];
for(i=1,j=0;i<row;i++)
    apple[i][j]=apple[i-1][j]+apple[i][j];

for(i=1;i<row;i++)
{
    for(j=1;j<column;j++)
    {
        if(apple[i][j-1]>=apple[i-1][j])
            apple[i][j]=apple[i][j]+apple[i][j-1];
        else
            apple[i][j]=apple[i][j]+apple[i-1][j];
    }
}
printf("\n maximum apple u can pick=%d",apple[row-1][column-1]);    

办法2：

结果是临时数组具有所有的插槽，最初为0。

int getMax(int i, int j)
{
    if( (i<ROW) && (j<COL) )
    {
        if( result[i][j] != 0 )
            return result[i][j];
        else
        {
            int right = getMax(i, j+1);
            int down = getMax(i+1, j);

            result[i][j] = ( (right>down) ? right : down )+apples[i][j];
            return result[i][j];
        }
    }
    else
        return 0;
}

方法3使用的空间最少：

它不使用任何临时数组。

int getMax(int i, int j)
{
    if( (i<M) && (j<N) )
    {
            int right = getMax(i, j+1);
            int down = getMax(i+1, j);
            return apples[i][j]+(right>down?right:down);
    }
    else
        return 0;
}

我想知道解决这个问题的最佳方法是什么？

Answer 1

方法1和方法2之间没有什么区别，方法1可能要好一点，因为它不需要用于方法2所使用的递归的堆栈，因为这是倒退的。

方法3的时间复杂度是指数级的，因此它比其他两个具有复合O(行*列)的方法要糟糕得多。

您可以使方法1的一个变体沿着对角线前进，只使用O(max{行，列})附加空间。

Answer 2

就时间而言，解决方案1是最好的，因为没有递归函数。递归函数的调用需要时间。

Answer 3

改进第一种方法

你真的需要临时数组是N乘以M吗？

不是的。

如果初始的二维数组有N列和M行，我们可以用长度为M的一维数组来解决这个问题。

方法

在您的第一种方法中，您保存了所有的小计，但当您移动到下一列时，实际上只需要知道左边和上面的单元格的苹果值。一旦你确定了这一点，你就不会再看那些以前的细胞了。

然后，解决方案是在下一列开始时重写旧值。

代码将如下所示(我实际上不是一个C程序员，所以请容忍我)：

“守则”

int getMax()
{
    //apple[][] is the original apple array
    //N is # of columns of apple[][]
    //M is # of rows of apple[][]
    //temp[] is initialized to zeroes, and has length M

    for (int currentCol = 0; currentCol < N; currentCol++)
    {
        temp[0] += apple[currentCol][0]; //Nothing above top row

        for (int i = 1; i < M; i++)
        {
            int applesToLeft = temp[i];
            int applesAbove = temp[i-1];

            if (applesToLeft > applesAbove)
            {
                temp[i] = applesToLeft + apple[currentCol][i];
            }
            else
            {
                temp[i] = applesAbove + apple[currentCol][i];
            }
        }
    }

    return temp[M - 1];
}

注意:没有任何理由将applesToLeft和applesAbove的值实际存储到局部变量中，并且可以随意使用分配的？：语法。

另外，如果列比行少，则应该将其旋转，这样一维数组的长度就更短了。

这样做是对第一种方法的直接改进，因为它节省了内存，加上对同一个一维数组的迭代确实有助于缓存。

我只能想出一个使用不同方法的理由：

多线程

为了在这个问题上获得多线程的好处，您的第二种方法几乎是正确的。

在第二种方法中，使用备忘录存储中间结果。

如果您使您的备忘录线程安全(通过锁定或使用无锁散列集)，那么您可以启动多个线程，所有这些线程都试图获得右下角的答案。

// Edit:实际上，由于将ints分配到数组是一种原子操作，所以我认为您根本不需要锁定。

每次调用getMax时，随机选择是否首先执行左getMax或高于getMax的操作。

这意味着每个线程在问题的不同部分工作，并且由于有备忘录，它不会重复不同线程已经完成的工作。