java - 用递归计算可能的坐标移动

Question

我正在尝试编写一个执行以下操作的方法:

public class GridCounting {
    /** Returns the total number of possible routes (paths) from
     * (x,y) to (tx,ty).
     * There are only three valid kinds of moves:
     *  Increment x by one.
     *  Increment x by two.
     *  Increment y by one.
     *
     *  Hint: You'll need to two base cases.
     */
    public static int count(int x,int y, int tx, int ty) {
        if (x==tx && y==ty)
            return 1;
        if (x>tx || y>ty)
            return 0;
        if (x<tx)
            return 1 + count(x+1, y, tx, ty);
        if (x<tx) //if x is still less, then we can do another move
            return 1 + count(x+2, y, tx, ty);
        if (y<ty){
            return 1 + count(x, y+1, tx, ty);
        }
        return 0;
    }
}

我遇到的麻烦是我总是差 +1。它期望 4，但我给它 5。令人困惑的部分是，如果我输入函数 count(10,15,10,15)，那么它仍然算作 1 步。我不知道如何解释这一点。

此外，y++ 然后 x++ 算作 1 步，x++ 然后 y++ 算作另一步。编辑:固定代码:

public static int count(int x,int y, int tx, int ty) {
    if (x==tx && y==ty)
        return 1;
    if (x>tx || y>ty)
        return 0;
    if (x<tx)
        return count(x+1, y, tx, ty) + count(x+2, y, tx, ty) + count(x,y+1,tx,ty);
    if (y<ty) {
        return count(x, y+1, tx, ty); // what does this do?
    }
    return 0;
}

Answer 1

我遇到的麻烦是我总是被 +1 打败。它期望 4，但我给它 5。
在位置 (x, y) 中，一般来说，我们有三种选择 (x+=1, x+=2, y+= 1)。它们每个都产生单独的路径，我们需要找到总共有多少条路径。
所以，这部分是错误的

        if (x<tx)
            return 1+ count(x+1, y, tx, ty);
        if (x<tx)
            return 1+ count(x+2, y, tx, ty);
        if (y<ty){
            return 1+ count(x, y+1, tx, ty);
        }
        return 0;

这是一个提示，如果您需要更多，请告诉我。

y++ 然后 x++ 算作 1 步，x++ 然后 y++ 算作另一步。
嗯，这对我来说听起来像是两条不同的道路。

编辑
好的，return count(x + 1, y, tx, ty) + count(x + 2, y, tx, ty) + count(x, y + 1, tx, ty); 是所有你需要的。
如果有 3 条路径从第一步 x + 1 开始，2 条路径从第一步 x + 2 开始，2 条路径从第一步 y + 1 开始，那么，显然，总共有 3 + 2 + 2 条路径。