7.3机器人走格子

有一个x*y的网格,一个机器人只能向右或向下走,要从左上角走到右下角.
请设计一个算法,计算机器人有多少种走法.
给定两个整数 int x,int y,请返回机器人的走法数目.保证x+y小于等于12.

递归思路:
最基本最基本的一种情况就是:

当x为1时,无论y是什么,都只有一种走法,就是向右走.
当y为1时,无论x是什么,都只有一种走法,就是向下走.

图片.png

递推公式就是,f(x,y) = f(x-1,y)+f(x,y-1)
f(x-1,y)代表的是向下走,那么面对的是x行少一行,但y列不受影响,面对的是(x-1)*y的网格.

迭代思路;

因为一个走法是被两个值确定的,即被x和y确定的
所以要用二维数组来存储,
为了方便,就多加一个数组长度,0角标的数组就不使用了
int[][] arr = new int[x+1][y+1]

当x为1时,无论y是什么,都只有一种走法,就是向右走.
当y为1时,无论x是什么,都只有一种走法,就是向下走.
所以初始化的基本问题是,
arr[1][i] = 1.第一行全为1
arr[j][1] = 1,第一列全为1

又因为递推公式
f(x,y) = f(x-1,y)+f(x,y-1).
那么arr[i][j] = arr[i-1][j]+arr[i][j-1]

图片.png

package _7节;

public class _7_3机器人走方格 {
    public static void main(String[] args) {
        System.out.println(move(6, 6));
        System.out.println(moving(6, 6));
    }
    /*
        迭代
     */
    public static int move(int x, int y) {
        int[][] arr = new int[x + 1][y + 1];
        for (int i = 1; i < y + 1; i++) {
            arr[1][i] = 1;
        }
        for (int i = 1; i < x + 1; i++) {
            arr[i][1] = 1;
        }
        for (int i = 2; i < x+1; i++) {
            for (int j = 2; j <y+1 ; j++) {
                arr[i][j]=arr[i-1][j]+arr[i][j-1];
            }
        }
        return arr[x][y];
    }
    /*
        递归
     */
    public static int moving(int x ,int y){
        if (x==1||y==1)
            return 1;
        return moving(x-1,y)+moving(x,y-1);
    }
}