c - 包含苹果的网格

Question

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

一张由 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]);    

方法二:

结果是临时数组，所有槽位初始为 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(rows*columns) 的其他两个要差得多。

您可以对方法 1 进行变体，沿对角线进行，以仅使用 O(max{rows,columns}) 额外空间。