首页 > 代码库 > [Jobdu] 题目1408:吃豆机器人
[Jobdu] 题目1408:吃豆机器人
- 题目描述:
淘宝公司内部有许多新鲜的小玩具,例如淘宝智能机器人。小时候,大家都玩过那个吃豆子的游戏吧,这机器人就是按照这个游戏设计的,它会朝着豆子的方向行走。不过机器人还存在一个bug,他只会朝南和朝东走。现在有一块空地,分成了n*m个格子,每个格子内有一颗豆子。机器人的起点在西北角,终点在东南角。请问机器人从起点到终点有多少种不同的方法。
- 输入:
每个案例输入只有一行,有n和m两个正整数,n,m均小于等于10^3。由于答案很大,所以答案对10009取余。
- 输出:
对于每个案例,输出一行,输出机器人从起点到终点的总方法数。
- 样例输入:
2 23 3
- 样例输出:
26
一开始想着排列组合,发现好复杂啊,后来发现其实跟跳台阶问题是一个道理,用递推就可以了。
1 #include <iostream> 2 using namespace std; 3 4 int n, m; 5 int a[1000][1000]; 6 7 void init() { 8 for (int i = 0; i < 1000; ++i) { 9 a[i][0] = 1;10 a[0][i] = 1;11 }12 for (int i = 1; i < 1000; ++i) {13 for (int j = 1; j < 1000; ++j) {14 a[i][j] = (a[i-1][j] + a[i][j-1]) % 10009;15 }16 }17 }18 19 int main() {20 init();21 while (cin >> n >> m) {22 cout << a[n-1][m-1] << endl;23 }24 return 0;25 }26 /**************************************************************27 Problem: 140828 User: hupo25029 Language: C++30 Result: Accepted31 Time:150 ms32 Memory:5424 kb33 ****************************************************************/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。