代码语言：javascript复制
import java.util.Scanner;
/**
* 机器人走方格
*
* 有一个X*Y的网格，-个机器人只能走格点，
* 且只能向右或向下走，要从左上角走到右下角。
* 请设计-个算法，计算机器人有多少种走法。
* 给定两个正整数int x,int y,请返回机器人的走法数目。
* 保证x y小于等于12。
*
*
* 先找规律：
* 发现
* 当前位置的走法 是 左边一格位置的走法 上边一格位置的走法
* f(x,y) = f(x-1,y) f(x y-1)
* 你返现2*2的时候还可以直接看出来 但是3*3的时候 就直接看不出来了
* 需要你想到 拿3*3的为例
* 你右走一步 下一步面临的就是3*2的样子 直接 加上3*2时的结果即可
* 此时你右走（x-1） 面临的是3*1 -----1种
* 下走（y-1） 面临的是2*2 -----2种
* 可以算出 3*2的时候 == 1 2 种
* 下走同上
* 可算出2*3的时候 == 1 2 种
* 可以算出3*3 == 6种
*
* 可以总结出：
* f(x,y) = f(x-1,y) f(x y-1)
*/
public class RecursionTest02 {
public static void main(String[] args) {
RecursionTest02 recursionTest02 = new RecursionTest02();
Scanner scanner =new Scanner(System.in);
System.out.print("input:");
int X = scanner.nextInt();
int Y = scanner.nextInt();
// 方法1
// System.out.println(recursionTest02.solution1(X,Y));
// 方法2
System.out.println(recursionTest02.solution2(X,Y));
}
/**
* 方法1
* 递归(简洁 但是隐藏了许多细节 看得人不容易理解)
* f(x,y) = f(x-1,y) f(x y-1)
* @param X
* @param Y
* @return f(x-1,y) f(x y-1)
*/
public int solution1(int X,int Y){
if (X<=0||Y<=0){return 0;}
else if (X==1||Y==1){return 1;}
else {
return solution1(X-1,Y) solution1(X,Y-1);
}
}
/**
* 方法2
* 迭代
* 这里不同于上一题走楼梯的是 那个传入的是1个参数
* 可以使用一维的结构去保存他们
* 而这里是2个参数 且 两个参数不同步变化
* 所以这里可以引入二维数组去解题
* 如下： Y
* ------------------
* 1 1 1 1 1
* ------------------
* 1 2 3
* ------------------
* 1 3 6
* ------------------
* 1
* ------------------
* X 1 (X,Y)
* ------------------
*
* @param X
* @param Y
* @return
*/
public int solution2(int X,int Y){
int [][] state= new int[X][Y];
if (X<0||Y<0){return 0;}
// 初始化第一列和第一行
for (int i = 0; i < X; i ) {
state[i][0] = 1 ;
}
for (int i = 0; i < Y; i ) {
state[0][i] = 1 ;
}
// 将给定的X*Y网格对应的各个位置走法 全部填入对应位置
for (int i = 1; i < X; i ) {
for (int j = 1; j < Y; j ) {
state[i][j] = state[i-1][j] state[i][j-1];
}
}
return state[X-1][Y-1];
}
}
