发布时间: 2016年9月13日 20:39 最后更新: 2016年9月20日 12:04 时间限制: 1000ms 内存限制: 128M
描述lhcoder有一个n行m列的棋盘，有一颗棋子从左上角(1,1)开始移动，每次只能往右或者往下移动一格，到右下角(n,m)一共有多少移动方案?
输入有多组测试数据，每组测试数据中有两个整数n和m(2 <= n, m <= 1000),代表为n行m列的棋盘。
输出一个整数p，代表从左上角(1,1)移动到右下角(n,m)的方案数,由于方案数可能比较大，结果请对99991取模。
样例输入1 复制 2 2 样例输出1 2 样例输入2 复制 2 3 样例输出2 3 查看隐藏信息很简单的一道题却做错了，大概是因为超时吧，两种很有趣的解法：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int mod=99991; int ans[1005][1005]; int n,m; int dfs(int x,int y) { if(ans[x][y]) { return ans[x][y]; } if(x==n&&y==m) { return 1; } long long ret=0; if(y+1<=m) { ret+=dfs(x,y+1); ret%=99991; } if(x+1<=n) { ret+=dfs(x+1,y); ret%=99991; } return ans[x][y]=ret; } int main() { while(~scanf("%d %d",&n,&m)) { memset(ans,0,sizeof(ans)); printf("%d\n",dfs(1,1)); } return 0; } #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int mod=99991; int num[1005][1005]; void init() { for(int i=1;i<=1000;i++) { num[1][i]=1;num[i][1]=1; } for(int i=2;i<=1000;i++) { for(int j=2;j<=1000;j++) { num[i][j]=(num[i][j-1]+num[i-1][j])%mod; } } return ; } int main() { init(); int n,m; while(~scanf("%d %d",&n,&m)) { cout << num[n][m] <<endl; } return 0; }简单的说就是很神奇的一些算法，他的灵活度还需自己慢慢体会（再一次感悟到了简单算法的博大精深，主要自己太菜 ）
