问题15－求n*n的网格，从左上角到右下角有多少线路

问题叙述如下：

“1个2*2的网格，从左上角到右下角有6条线路（不可回头），如图所示

请问，一个20*20的网格，从左上角到右下角有多少条线路。”

 

代码实现如下：

 

/**
	 * 对于一个n*n的网格，从左上角到右下角有多少条线路
	 * 
	 * @param n
	 */
	private static Long getRouteSize(int n) {
		Long[][] a = new Long[n + 1][n + 1];// 注意int长度不够
		for (int i = 0; i <= n; i++) {
			Arrays.fill(a[i], 0L);
		}
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				if (i == 0 && j != 0) {
					a[i][j] = a[i][j - 1];
				} else if (i != 0 && j == 0) {
					a[i][j] = a[i - 1][j];
				} else if (i == 0 && j == 0) {
					a[i][j] = 1L;
				} else {
					a[i][j] = a[i - 1][j] + a[i][j - 1];
				}
			}
		}
		return a[n][n];
	}

  可以得到答案：137846528820

 

请不吝赐教。

@anthor ClumsyBirdZ

 

评论

1 楼 stef3390 2011-01-19  

你好，请问能解释下这个算法吗？我看了很久没有弄懂啊