题目描述
有一个X*Y的网格，一个机器人只能走格点且只能向下或向右走，要从左上角走到右下角。 请设计一个算法，计算机器人有多少种走法。 给定两个正整数int x,int y，请返回机器人的走法数目，保证x＋y小于等于12。
分析
先假如只有1个格子，那很明显只有一种走法，那么我们再去画 12，21，13，31，也只有1种走法，再去画22 的方格，发现有两种走法了。
当22的时候发现他是由12 和21构成.....
所以
我们根据分析就可以得出这个递推式f(x,y)=f(x-1,y)+f(x,y-1)（因为只能向右走和向下走）
所以我们可以使用递归的方式来解决这个问题，其次我们也可以使用迭代(递推)的方式来解决，因为涉及到两个变量都在变化，使用一维的变量是不能够保存的，所以要使用二维的数据结构：二维数组来保存从起始点到某一点的走法，比如说a[2][3]=3，表示机器人到这一个点总共有3种走法。
使用递归的话就相当于一种富人的思想，把什么都交给手下人去做，自己只负责合并结果，代码很简洁。而迭代(递推)相当于打工者的思想，一步步根据自己的分析得出想要的结果，代码相对来说比递归要复杂一点。
代码
package BlueCup.Seven_recursion;
import java.util.Scanner;
public class _703_机器人走方格 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int x = cin.nextInt();
int y = cin.nextInt();
int ans = f(x, y);
System.out.println(ans);
}
private static int solve(int x, int y) {
//顺着想 倒着写
if (x == 1) return 1;
if (y == 1) return 1;
return solve(x - 1, y) + solve(x, y - 1);
}
/**
* 迭代形式
*/
//dp公式 f(x,y)=f(x-1,y)+f(x,y-1);
//当x或y=1时 无论怎样都只有一部
public static int f(int m, int n) {
int[][] state = new int[m + 1][n + 1];//缓存 想染色
for (int i = 1; i <= n; i++) {//每一列的第一行
state[1][i] = 1;
}
for (int i = 1; i <= m; i++) {//每一行的第一列
state[i][1] = 1;
}
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
state[i][j] = state[i][j - 1] + state[i - 1][j];
}
}
return state[m][n];
}
}
本文作者：Author： 寒光博客
文章标题：[CC150]902机器人走方格问题
本文地址：https://dxoca.cn/Algorithm/205.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/Algorithm/205.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
链接：https://www.nowcoder.com/questionTerminal/e8bb8e68434e42acbcdff0341f2a32c5
来源：牛客网
考虑原始DP问题为二维数组表示当前位置的步数，显然有: dp[i][j] = dp[i-1][j] + dp[i][j-1]，而容易发现dp数组可以压缩为1维存储空间dp[y]。原dp[i-1][j]为上一行当前列的步数，而现dp[j]就存储了上一次该列的步数，而现dp[j-1]为左节点的步数即原dp[i][j-1]。
所以变为：dp[j] = dp[j] + dp[j-1].
10月就要奥赛了，加油！
先顶过9月的物理再说 
加油 加油！！
恩。一起努力