一、原题
从2×2网格的左上角开始，并且只能向右和向下移动，到右下角正好有6条路线。
通过给定的网格n * n有多少条这样的路线？
二、解题思路
方法1：
这道题第一眼给我的感觉是分治法去处理，从起点开始，
若到达终点即 (i,j)==(n,n) 则为一条路径；
若行到达最下方 (i,j)==(n,j) 则只有向右 j++ 一种走法；
若到达最右方 (i,j)==(i,n) 则只有向下i++一种走法；
否则，每一个点都有向下、向右两种走法，即 (i+1,j) 和 (i,j+1)；
于是有了第一次提交的版本
function latticePaths(gridSize) {var count = latticePathsDivide(0,0,gridSize);console.log(count);return count;
}function latticePathsDivide(i,j,n){if(i==n&&j==n) return 1;if(i==n) return latticePathsDivide(i,j+1,n);if(j==n) return latticePathsDivide(i+1,j,n);return latticePathsDivide(i+1,j,n) + latticePathsDivide(i,j+1,n);
}latticePaths(9);然而，这种方法跑 n=20 时候跑不出结果，于是就想了第二种方法
方法2：
将网格旋转45°，可以发现这与二叉树很像，只不过它有共同的子节点，将二叉树从根节点走到叶节点
这种方法遇到的第一个难题是怎么保存已经走过的路径，参考树的遍历，我想到了栈，由于js不是很熟，于是手动补了一些方法；
接下来是这个算法烧脑的部分，怎么用栈避免重复路径呢？参考一下二叉树的先序遍历，我们可以把每个点看作树的节点，先遍历左节点，再遍历右节点
第二次提交版本
function latticePaths(gridSize) {var count = 0; //到达叶节点的次数，也是最终的路径数var arr = []; //保存路径的栈var i=0,j=0; //进入while循环的节点var prevPoint; //进入while循环的节点的上一个节点arr.push([0,0]); //先放入根节点while(!arr.empty()){ //若栈不为空，则遍历完成所有节点while(i<gridSize) arr.push([++i,j]); //先遍历左节点while(j<gridSize) arr.push([i,++j]); //再遍历右节点if(i == gridSize && j == gridSize) { //判断是否到达终点//console.log(arr); //关键点在这里，如何确定下一个遍历的点count++;arr.pop(); //将路线数加一，将终点出栈while(arr.top().compare([i-1,j])){ //先回退左节点arr.pop();i--;};while(arr.pop().compare([i,--j])){ //回退右节点if(arr.empty()) break;prevPoint=arr.top();if(!prevPoint.compare([i,j-1])){ //当回退的右节点不在栈中，确定下一个节点，找下一条路线i = prevPoint[0];j=prevPoint[1]+1;//console.log([i,j]);arr.push([i,j]);break;}}}}console.log(count);return count;
}Array.prototype.top = function () {return this[this.length-1];
}Array.prototype.empty = function () {return this.length <= 0;
}Array.prototype.compare = function() {if(this.empty()) return false;return arguments[0].toString() == this.toString() ? true : false;
}latticePaths(9);然而，这种方法跑 n=20 时候也跑不出结果，脑子有点不够用了，就到网上搜了一下，就是下面的第三种方法
方法3：
分析题目，要到达某个点，必然会先到达其左边或者上边的点，故该点的路径数等于其左边点的路径数加上其上边点的路径数；
n = 0时，只有一个点，故 (0,0) 的值为1，而 (i,0) 和 (0,j) 均只能从单方向到达，故它们的值也是1， (1到n, 1到n) 所有点的，它们的值按上面的结论计算
第三次提交版本
function latticePaths(gridSize) {var count = 0;var arr = [];var arrTemp = [];//初始化数组for(var i=0;i<=gridSize;i++){arrTemp=[];for(var j=0;j<=gridSize;j++){arrTemp.push(0);}arr.push(arrTemp);}for(var i=0;i<=gridSize;i++){arr[0][i]=1;arr[i][0]=1;}//console.log(arr);//推结果for(var i=1;i<=gridSize;i++){for(var j=1;j<=gridSize;j++){arr[i][j]=arr[i-1][j]+arr[i][j-1];}}count = arr[gridSize][gridSize];console.log(count);return count;
}latticePaths(20);这次完美通过。