题目描述
有一个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];
}
}
本文地址: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月的物理再说
加油 加油!!
恩。一起努力