通过递归计算可能的坐标移动

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++ 算作另一步。
嗯，这对我来说听起来像是两条不同的道路。

编辑
好的，返回 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 条路径。

Answer 2

你确定这条线是对的吗？

if (x==tx && y==ty)
  return 1;

看起来它应该返回零。

在手机上，所以无法测试。

Answer 3

if (x==tx && y==ty) return 1; 听起来不正确。如果您已经到达目的地，则没有更多路线。

Answer 4

也许我不理解规则，但我认为这是第一个基本情况导致了你的问题。如果您已经到达该位置，那么您就不会采取行动。