c - 单调路径面积的递归和

Question

我试图想出一种递归方法来找到从 nxn 网格的左上角到右下角的所有单调路径的所有面积的总和(路径的每一步可以向右或向右)沿着线向下)。

假设左下角坐标为(0,0)，我有以下函数:

int sum(int current_sum, int x, int y, int n){
    if (x == n || y == 0)  
        return current_sum;

    return (sum(current_sum+y, x+1, y, n) + sum(current_sum, x, y-1, n));
}

，当它到达网格的右侧或底线时停止(从那里开始的任何移动都不会改变区域的当前值)并考虑向右或向下移动所产生的区域总和。结果比应有的要大，我很难弄清楚为什么。有人可以看一下吗？

提前致谢

Answer 1

再读一遍，OP的解决方案似乎已经是正确的了。我的回答如下供引用。

<小时/>

这似乎是欧拉计划problem 15 ，或非常类似的问题。

所以，如果我理解正确的话，你想做的是:

1. 沿着每条路径精确地走一次。
2. 计算每条不同的路径，并将该路径下的面积添加到总和中。

以递归方式执行此操作将如下所示:

int area(int x, int y)
{
  if (x == 0 || y == 0)
    /* We are at the end of a path, terminate */
    return 0;

  /* We are not at the end, add the two choices possible from here */
  return area(x, y - 1) + area(x - 1, y) + y;
}

你必须画一个图来看看最后的表达式是否正确。仅当我们在网格中向右移动 (-x) 时，我们才会将 y 添加到总和中，从而覆盖我们下方的一列。向下移动 (-y) 不覆盖任何区域。

这个解决方案应该是正确的，但是会很慢。为了加快速度，您可以添加内存，这意味着将area(x, y)的中间结果保存到表中并查找，而不是每次都计算它。我不会为你写这个解决方案，但这并不难。祝你好运。