题目:
x*y的方格,从A点到B点,A点只能想下或者向右,求共有几条不重复路径,打印出路径
如图所示
其实这是数学排列组合中的题目数学公式如下
不适用公式计算的话,如何计算?
我用的是递归的方法代码如下:
static int row = 100; static int line = 100; static Integer[][] source = new Integer[row][line]; static int startI = 0; static int startJ = 0; static int endI = 4; static int endJ = 4; static int num = 0; static ArrayList<Integer> temp = new ArrayList<>(); static ArrayList<String> route = new ArrayList<>(); public static Integer[][] getSource() { int val = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < line; j++) { source[i][j] = val; val++; } } return source; } public static void main(String[] args) { getSource(); deal(startI, startJ); System.out.println(num); System.out.println(route); } public static void deal(int i, int j) { if( i <= endI && j <= endJ){ temp.add(source[i][j]); } if (i == endI && j == endJ) { route.add(temp.toString()); num++; } if (i > endI || j > endJ) { return; } deal(i + 1, j); if( i + 1 <= endI && j <= endJ){ temp.remove(source[i + 1][j]); } deal(i, j + 1); if( i <= endI && j + 1 <= endJ){ temp.remove(source[i][j + 1]); } }