用于实现格路径计数的递归

Question

我正在尝试使用递归解决在格子(某个网格(中查找路径数的问题。

我编写了以下代码，假设在格子/网格中找到有效路径的总数。在有效路径(网格的右下角(中，您只能向以下两个方向之一移动：向右或向下。

我不确定这是使用递归的正确方法。有没有更好的方法来解决这个问题/使用递归来解决这个问题？

谢谢

var array = [[0,0,0,0],[0,0,0,0],[0,0,0,0]];
var lastRowIndex=2;
var lastColIndex=3;
var count=0;
function pathCount(i,j){
if(!(array[i-1]==undefined) || !(array[i][j-1]==undefined)){
if(!(array[i-1]==undefined)){
--i;
pathCount(i,j);
i++;
}
if(!(array[i][j-1]==undefined)){
--j;
pathCount(i,j); 
}
}else{
++count;
}
return count;
}
console.log(pathCount(lastRowIndex,lastColIndex));

Answer 1

你的代码很好。 基本上它做了它应该做的事情。

假设仅通过向下移动网格或向右移动来构造有效路径， 请注意，您实际上并不需要数组，只需要一个大小参数和一个指向算法行进的当前位置的指针。

与任何回归问题一样，让我们从简单的东西开始，归纳基础。

首先请注意，在线性网格(大小为 1xN 或 Nx1(中，只有一条有效路径。 现在，如果你在(i，j(广场，你只有2种移动的可能性，因此 路径总数是两个元素的总和：

1. 从正方形 (i-1，j( 开始的有效路径数
2. 从正方形 (i，j-1( 开始的有效路径数

(请注意，需要对这些参数进行有效性检查，因为它们受网格的可能索引的限制(。

所以可能的递归是：

let size = 10;
let grid = {
width: size,
height: size
};
let currentPosition = {
x: size,
y: size
};
function validDecrement(value) {
return (value - 1 >= 1 ? value - 1 : 1);
}
function countValidPaths(gridObject, startingLocation) {
if (startingLocation.x === 1 || startingLocation.y === 1) {
return 1;
} else if (startingLocation.x > 1 && startingLocation.y > 1) {
return countValidPaths(gridObject, {
x: startingLocation.x,
y: validDecrement(startingLocation.y)
}) + countValidPaths(gridObject, {
x: validDecrement(startingLocation.x),
y: startingLocation.y
});
} else {
console.log(`invalid input: grid: ${gridObject}, startingLocation: ${startingLocation}`);
};
}
console.log(`Number of valid paths over a ${grid.height} by ${grid.width} grid is : ${countValidPaths(grid,currentPosition)}`);

当然 - 有一种更好的方法来解决这种方法，而不是递归。 您要查找的数字只是二项式系数C((grid.with-1)+(grid.height-1),(grid.width-1))- 晶格路径计数