java - 获取 n x n 网格中所有可能的下边缘和右边缘路径

Question

问题 15:
从 2×2 网格的左上角开始，到右下角有 6 条路线(没有回溯)。
通过 20×20 网格有多少条路线？

所以我尝试 Problem 15有点蛮力，因为我试图通过从右到左移动并更改第一次改变方向的前导来获得所有可能有效路径的排列。例如，当我有一个 2x2 网格时(查看问题 15 链接图形)，我将采用的第一条路径是 right - right - down - down 而我将采用的最后一条路径是 < strong>down-down-right-right，这也是我的终止标准。我将可能的有效路径添加到列表中，并使用该列表来确定是否已添加有效路径。为了排列路径，我将执行我之前提到的操作:我在我的数组中从右到左移动(在图形中箭头指向的右下角)并更改其中的第一个元素下一个元素与自身不同。所以 right - right - down - down 会变成 right - right - right - down，这显然是无效的，因为你必须拥有相同数量的右和下才能能够到达终点角。所以我的想法是让另一个循环从左到右并根据需要更改尽可能多的元素以获得有效路径。所以在这个例子中 right - right - right - down 变成了 down - right - right - down。

此外，我忘记了我不是在计算点数，而是在计算从左上角到右下角的边。

所以我已经写了一些代码，但是根本不起作用。

package projecteuler;

import java.util.ArrayList;

public class Projecteuler {
    public static final int GRIDSIZE = 2;

    public static void main(String[] args) {
        ArrayList<boolean[]> paths = new ArrayList<>();

        paths.add(new boolean[GRIDSIZE * 2]);
        for(int i = 0; i < GRIDSIZE; i++) {
            paths.get(0)[i] = true;
            paths.get(0)[GRIDSIZE * 2 - 1 - i] = false;
        }

        boolean[] buf = paths.get(0).clone();
        printArr(buf);
        boolean tmp;
        while(!checkTerminate(paths)) {
            while(paths.contains(buf)) {
                tmp = buf[buf.length - 1];
                for(int i = buf.length - 1; buf[i - 1] != tmp && 0 < i; i--) {
                    buf[i] = !buf[i];
                    for(int j = 0; checkValid(buf) && j < i; j++)
                        buf[j] = !buf[j];
                }
            }
            paths.add(buf.clone());
            printArr(buf);
        }
        System.out.println(paths.size());
    }

    public static boolean checkTerminate(ArrayList<boolean[]> paths) {
        boolean[] endPath = new boolean[GRIDSIZE * 2];
        for(int i = 0; i < GRIDSIZE; i++) {
            endPath[i] = false;
            endPath[GRIDSIZE * 2 - 1 - i] = true;
        }
        return paths.contains(endPath);
    }

    public static boolean checkValid(boolean[] arr) {
        int countR = 0,
            countL = 0;
        for(int i = 0; i < arr.length; i++) 
            if(arr[i])
                countR++;
            else
                countL++;

        return countR == countL;
    }

    public static void printArr(boolean[] arr) {
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] ? "right " : "down ");
        System.out.println();
    }
}

它在某种程度上不会改变任何地方。

right right down down 
right right down down 
right right down down 
right right down down ...

等等就是它的输出。看起来代码根本不会改变我的路径，但也不会卡在任何 for 循环中。我最好的猜测是我的函数标准放置在错误的顺序中

我也想到了一个回溯解决方案，就像我们两年前在学校做的迷宫一样，但我想在重做所有事情之前看看这种方法是否可行。

编辑:
我会尽快实现 2 x 2 网格示例的图像，但 ProjectEuler 网站目前正在维护中。

Answer 1

解决方案由我们可以拥有的“向下”和“向右”运动的组合数量给出。由于没有回溯，总共有 N 向下和 N 向右移动(在任何 route ，对于 NxN 网格)。总共有 2N 个 Action 。

我们可以使用二项式系数，ⁿC_r(发音为“n choose r”)得到这个值，它是从 n 对象中选择 r 对象的方法(每个可以是两个东西)。在我们的例子中，“对象”是向下或向右的运动。这是由

因此我们想要的数字是:

对于 N = 2 这给出 6。对于 N = 20，这将给出 137846528820。