单调路径区域的递归求和

-4

我想要一个递归的方法来找到从nxn网格的左上角到右下角的所有单调路径的所有区域的总和（每一步的路径可以沿着线条向右或向下）。单调路径区域的递归求和

假设左下角的坐标为（0,0），I具有以下功能：

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)); 
}

，当它到达任一网格的右侧或底部线（任何移动停止从那里不会改变该地区的当前价值），并考虑右移或下移导致的面积总和。结果是比它应该更大，我有一些困难，找出原因。任何人都可以看看吗？

在此先感谢

来源

2016-02-12 Vmf

我认为加上与输入一个具体的例子，预期和实际产量将有很大的帮助。 –

这是欧拉工程的一个问题：https://projecteuler.net/problem=15 – jforberg

重点关注回报。 x + 1，y-1。如何使用2步循环，x从低到高，y从高到低移动？它可以解决移动到零价值的问题。 –

再次阅读，OP的解决方案似乎是正确的了。我的答案在下面供参考。

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

所以，如果我理解正确的话，你想做的事是这样的：

按照每个通道一次。
统计每个不同的路径并将该路径下的区域添加到总和。

以递归的方式这样做应该是这样的：

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）不包括任何区域。

此解决方案应该是正确的，但它会很慢。要加快速度，您可以添加备忘录这意味着将区域（x，y）的中间结果保存到表中并查找它，而不是每次计算它。我不会为你写这个解决方案，但这并不难。祝你好运。

来源

2016-02-12 14:40:13 jforberg

[..]从n×n个网格的左上角至右下角 [..]

您的代码并不反映：

// ... 
    if (x == n || y == 0) 
    return current_sum; 
// ...

第一个单元格（右转）是问题：在那里，x == 2 == n因此您返回的路径总数为，尽管它没有在右下角结束。因此，你总结了太多路径，导致整体总和过大。

我想这应该这样做：

unsigned sum_inner(
    unsigned const accumulatedSum, 
    size_t const x, size_t const y, 
    size_t const gridSideSize) { 
    bool atRightEdge = (x == gridSideSize - 1); 
    bool atBottomEdge = (y == 0); 
    if (atRightEdge && atBottomEdge) { 
    // Awesome, in lower right corner, so everything is fine 
    // Except that with the implementation of the other two edge cases, this 
    // will never be run (except for the 1x1 case)! 
    printf("reached lower right edge!\n"); 
    return accumulatedSum + 1; 
    } else if (atRightEdge) { 
    // Right edge, so from here one can only go down. Since there's only one 
    // possible path left, sum it directly: 
    return accumulatedSum + y + 1; 
    } else if (atBottomEdge) { 
    // Bottom edge, so from here one can only go right. Since there's only one 
    // possible path left, sum it directly: 
    return accumulatedSum + (gridSideSize - x) + 1; 
    } else { 
    // Somewhere in the grid, recursion time! 
    return sum_inner(accumulatedSum + y, x + 1, y, gridSideSize) + 
      sum_inner(accumulatedSum, x, y - 1, gridSideSize); 
    } 
} 

unsigned sum_monotonic_tl_br(size_t const gridSideSize) { 
    return sum_inner(0, 0, gridSideSize - 1, gridSideSize); 
}

(Live with sizes from 1 to 15)

来源

2016-02-12 18:15:10

单调路径区域的递归求和

回答

相关问题