机器人从最左上角走到最右下角的问题.pdf

机器⼈从最左上角出发，只能向下或向右⾛，每次⾛⼀步，⾛到最右下角，有多少种⾛法？递归解法：找规律：当你向右⾛时，列数减⼀。当你向下⾛时，⾏数减⼀。总的路径⾛法：两者相加当只有⼀⾏或者⼀列，只有⼀种⾛法⾮递归解法：即state[i][j] = state[i-1][j]+state[i][j-1]代码： package Recursion; / 两种⽅式：递归和迭代，迭代利⽤⼆维数组 f(x,y)=f(x-1,y)+ f(x,y-1) * / public class机器⼈从最左上角走到最右下角的问题{ //递归public static int jiqiren(int x,int y){ //当只有⼀⾏或者只有⼀列的时候，只有⼀种⾛法，递归的出⼝ if(x==1""y==1) return 1; return jiqiren(x-1,y)+jiqiren(x,y-1); } //迭代public static int jiqiren1(int m,int n){ int[][] state=new int[m+1][n+1]; //定义⼀个⼆维数组，从1，1开始，0，0的不要了m代表⾏，n代表列for (int i = 1; i <=n ; i++) { state[1][i]=1; //初始化只有⼀⾏的时候只有⼀种⾛法} for (int i = 1; i <=m ; i++) { state[i][1]=1; //初始化只有⼀列的时候只有⼀种⾛法} //注意：i，j开始的起点坐标是（2，2） for (int i = 2; i <=m ; i++) { for (int j = 2; j <=n ; j++) { state[i][j]=state[i-1][j]+state[i][j-1]; //f(x,y)=f(x-1,y)+ f(x,y-1) } } return state[m][n]; } public static void main(String[] args) { int sum = jiqiren1(3, 3); System.out.pr