c - 递归计算从 (0,0) 到 (x,y) 的格子路径数

Question

有谁知道我如何编写一个递归函数来获取无符号整数 x, y 并返回 C 中从 0,0 到点 x,y 的路径数？

每次只有一步：向上或向右。步数的限制在矩形内：(0,0), (0, x), (0,y), (x,y)

Answer 1

对不起，这不是C，但你应该很好理解。以美元开头的都是变量，其余的都是类似的。

function path($x, $y){
    if($x==0 && $y==0){ /* && is logical AND operator */
        return 1;
    // here's first (and only) edge case. If X and Y is 0, that means were are already where we want to be. We assume there's one path from the position you are on to the same position you are on.
    }

    $count=0;

    if($x>0){
        $count+=path($x-1, $y); // Here, we ask how many paths go from position (x-1, y) to zero, if the X is not zero already..
    }
    if($y>0){
        $count+=path($x, $y-1); // here same stuff for Y, if Y is not zero, let's recurse into (x, y-1)
    }

    return $count; // in those conditions above, the result is added into COUNT variable
}

$x=6; 
$y=4; // some input


print path($x, $y); // here it all starts, with the original input numbers

它背后没有数学，它是一个递归。在 path() 函数的每次运行中，path 函数都会运行 path 函数的另一个实例，然后运行另一个实例，然后运行另一个实例。... 位置总是比当前位置小一，在一个维度上，然后在一个维度上小一个另一个维度。仅当递归已经到达 (0,0) 位置时，它才会返回 1，该值将添加到前一个实例中的 count 变量中，该值将添加到前一个实例中的 count 变量中，依此类推，直到它返回给打印函数。

注意：函数不是从 (0,0) 到 (x,y) 而是从 (x,y) 到 (0,0)。但结果是一样的。

Answer 2

Java解决方案：

/**
 * Compute the number of ways you can get from 0,0 to x,y
 *
 * @param x grid width
 * @param y grid height
 * @return number of lattice paths
 */
public long compute(int x, int y) {
    // there's only 1 way you can reach a point which is on some edge
    if (x == 0 || y == 0) {
        return 1;
    }
    /* Otherwise apply back recursion, i.e. take the last step (when you reach x,y) :
    you can get there only by moving from x-1,y (right) or from x,y-1 (up).
    So the result would be the number of ways you can get to x-1,y plus the number 
    of ways you can get to x,y-1 */
    return compute(x - 1, y) + compute(x, y - 1);
}

随着网格面积的增长（x 和 y），算法变得非常慢，因为由于递归，您多次计算相同的值，因此您可能需要缓存：

Map<Pair, Long> cache = new HashMap<>();

public long compute(int x, int y) {
    Pair pair = new Pair(x, y);
    if (cache.containsKey(pair)) {
        return cache.get(pair);
    }
    if (x == 0 || y == 0) {
        return 1;
    }
    long result = compute(x - 1, y) + compute(x, y - 1);
    cache.put(pair, result);
    return result;
}

Pair 是一个遵循equals() 和 hashCode() Contract的简单 POJO 。