java - 我的 euler Project 函数结果错误

Question

我正在尝试寻找欧拉问题 n°15 的解决方案。 http://projecteuler.net/problem=15(找出从网格的左上角到右下角的路径数)。

第一次尝试不成功，因为我将所有可能的组合存储在一个列表中，我最终遇到了堆问题(可以预见，不是吗)。

在第二次尝试中，我决定计算网格中每个点存在多少种可能的方式。例如(0,0)有唯一的访问方式，(1,1)有两个(通过(0,1)和另一个通过(1,0))。对于每一点，我们将前两点的可能方式相加。由于这似乎是一个没有太多内存问题的好解决方案，我仍然没有得到正确的答案，你能给我提示我错误的根源吗(因为我假设我犯了错误，而不是他们显然犯了错误)。

Snafucated 源代码:

    @Test
public void testFoo() {
    long[][] grid = new long[20][20];
    for(int i=0; i<20; i++){
        grid[0][i]=1;
        grid[i][0] =1;
    }
    int steps=1;
    while(steps<21){
        for(int i=steps; i<20; i++){
            grid[i][steps]= grid[i-1][steps]+grid[i][steps-1];
            grid[steps][i]= grid[i-1][steps]+grid[i][steps-1];
        }
        steps++;
    }
    System.out.println(grid[19][19]); //35345263800
}

Answer 1

在 2 × 2 网格中，有 3 × 3 个交点，所以你需要一个 3 × 3 数组。

  0 1 20 ┌─┬─┐1 ├─┼─┤2 └─┴─┘

因此对于 20 × 20 网格，您需要一个 21 × 21 数组。

---

另一种解决方案:使用数学中的组合，答案是 .