21Nod 1118 机器人走方格 【简单dp】
M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。
输入
第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000)
输出
输出走法的数量。
输入样例
2 3
输出样例
3
拿到题目就知道这是一道dp 递归也能解 但是容易TLE 思路很简单 dp三步
1。确认初始状态 很简单 边界条件 就是一路向下 和一路向右 也就是 i=1 和j=1 的格子只有一条路能走
2.寻找状态转移方程 到达第i行第j列 只能从第i-1行第j列和第i行第j-1列 走一步 所以到第i行第j列 的路的数量就是 第i-1行第j列和第i行第j-1列路的和 也就是 dp[i][j] = dp[i-1][j]+dp[i][j-1]
3.确定边界条件 边界条件很明显 就是表格的最右和最下
这道题就解出来了
上代码
#include<iostream>
using namespace std;
const int N = 1000+5;
const int MOD = 1e9+7;
int dp[N][N];
void Dp(int m,int n){
for(int i = 1; i <= m ;i++ ){
for(int j = 1; j <= n ; j++){
if(i == 1 || j == 1){
dp[i][j] = 1;
}else{
dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;
}
}
}
}
int main()
{
int m,n;
scanf("%d%d",&m,&n);
Dp(m,n);
printf("%d",dp[m][n]);
return 0;
}