c - 包含苹果的网格

我在一个编程论坛上发现了这个问题：
给出了一个由n*m个单元组成的表格，每个单元有一定数量的苹果。你从左上角开始在每一步，你可以向下或右一个细胞。设计一个算法来找出你可以收集的最大数量的苹果，如果你是从左上角移动到右下角。
我已经想到了三种不同的复杂性（在时间和空间上）：
接近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;
}

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

最佳答案

方法1和方法2之间没有什么区别，方法1可能稍微好一点，因为它不需要堆栈来进行方法2使用的递归，因为这是向后的。
方法3具有指数时间复杂度，因此比其他具有复数O（行×列）的情况要差得多。
您可以使方法1的变体沿着对角线前进，以仅使用O（max{rows，columns}）的额外空间。

关于c - 包含苹果的网格，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11613992/