51Nod_1118 机器人走方格【基础DP】

本文主要是介绍51Nod_1118 机器人走方格【基础DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                             51Nod_1118 机器人走方格

                                               http://www.51nod.com/Challenge/Problem.html#!#problemId=1118

题目

M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。

输入

第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000)

输出

输出走法的数量。

样例输入

2 3

样例输出

3

分析

动态规划求解，dp[i][j]表示走到坐标为(x,y)的位置的方案数，则由于只能向右向下走，因此dp[i][j]=dp[i][j-1]+dp[i-1][j],初始条件是dp[1][1]=1

C++程序

#include<iostream>using namespace std;const int MOD=1e9+7;
const int N=1000;
long long dp[N+1][N+1];int main()
{int n,m,i,j;scanf("%d%d",&n,&m); dp[1][1]=1;//第一个位置只有一种走法 for(i=1;i<=n;i++)for(j=1;j<=m;j++)dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i][j-1])%MOD;printf("%lld\n",dp[n][m]);return 0;
}

 

这篇关于51Nod_1118 机器人走方格【基础DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---