九度oj1408吃豆机器人

时间限制：1 秒

 

内存限制：32 兆

 

特殊判题：否

 

提交：778

 

解决：149

 

题目描述：

淘宝公司内部有许多新鲜的小玩具，例如淘宝智能机器人。小时候，大家都玩过那个吃豆子的游戏吧，这机器人就是按照这个游戏设计的，它会朝着豆子的方向行走。不过机器人还存在一个bug，他只会朝南和朝东走。现在有一块空地，分成了n*m个格子，每个格子内有一颗豆子。机器人的起点在西北角，终点在东南角。请问机器人从起点到终点有多少种不同的方法。

 

输入：

每个案例输入只有一行，有n和m两个正整数，n，m均小于等于10^3。由于答案很大，所以答案对10009取余。

 

输出：

对于每个案例，输出一行，输出机器人从起点到终点的总方法数。

 

样例输入：

2 2

3 3

样例输出：

2

6

 

2012年九度互动社区淘宝实习生春季招聘上机考试

一看数据量这么大，1000*1000.。。

 

果断放弃一般的搜索。

 

还有我们发现它的答案是只有这几种。。

 

就是说可以打表操作。

 

而且我们一般看到这种大数据操作就应该要想到用动态规划。。

 

没办法，高效。。。

 

dp[i][j] 代表有i行j列的总数是多少。。

 

所以我们很容易就想出状态方程是

 

dp[i][j] = dp[i-1][j]+dp[i][j-1]

 

 

 

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
long long dp[1004][1004];  
void Init()  
{  
    int i,j;  
        for(i=1;i<=1002;i++)  
        {  
        dp[i][1] = dp[1][i] = 1;  
        }      
          
        for(i=2;i<=1002;i++)  
        {  
        for(j=2;j<=1002;j++)  
        {  
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%10009;  
        }      
        }      
}      
int main()  
{  
    int row,col;    
    Init();  
    while(scanf("%d%d",&row,&col)!=EOF)  
    {  
        printf("%lld\n",dp[row][col]%10009);  
    }      
    return 0;  
}      

 

 

很简单的代码。。。

 

补充：软件开发 , C++ ,