我正在尝试寻找欧拉问题 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
}
最佳答案
在 2 × 2
网格中,有 3 × 3
个交点,所以你需要一个 3 × 3
数组。
0 1 2 0 ┌─┬─┐ 1 ├─┼─┤ 2 └─┴─┘
因此对于 20 × 20
网格,您需要一个 21 × 21
数组。
另一种解决方案:使用数学中的组合,答案是 .
关于java - 我的 euler Project 函数结果错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18231803/