51Nod系列

• 51Nod题解文章目录
• • [3218 机器人走方格 V5](http://www.51nod.com/Challenge/Problem.html#problemId=3218)
  • • 题目描述
    • 输入
    • 输出
    • 数据范围
    • 输入样例
    • 输出样例
    • 解题思路
    • Code
    • 小结

1级题

M∗N的方格，一个机器人从左上的格子走到右下的格子，即从初始位置 (1,1) ，走到结束位置 (m,n)。每步只能向右一格、或向下一格、或向右下一格走。有多少种不同的走法？

由于方法数量可能很大，只需要输出mod 109+7的结果。

第一行输入两个数M,N，以空格隔开。（2≤m,n≤1000)

输出一个数，走法的数量。

对于45%的数据，2≤m,n≤20；
对于100%的数据，2≤m,n≤1000；

2 3

5

这个是一个简单的dp 问题。 首行首列初始化为1. 这里出题者要求dp[1][1] =1, 我个人认为dp[1][1] =0, 这点需要再讨论。
递推公式如下： d p [ i ] [ j ] = ( d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] + d p [ i − 1 ] [ j − 1 ] ) dp[i][j]= (dp[i-1][j] +dp[i][j-1]+dp[i-1][j-1])%Mod dp[i][j]=(dp[i−1][j]+dp[i][j−1]+dp[i−1][j−1])

#include 
#include 
#include 
typedef long long LL;

using namespace std;
LL Mod = 1e9 +7;

LL dp[1010][1010];

int main()
{
    
    for (int i = 1; i <= 1000; i ++ )
        dp[1][i] =1, dp[i][1]=1;
    // dp[1][1]=0;
    int m,n;
    cin >> m >>n;
    for (int i = 2; i <= m; i ++ )
        for (int j = 2; j <= n; j ++ )
        {
            dp[i][j]= (dp[i-1][j] +dp[i][j-1]+dp[i-1][j-1])%Mod;
        }
    cout << dp[m][n];
    return 0;
}

例如：以上就是今天要讲的内容，本文仅仅简单讲解了3218 机器人走方格 V5解题方法以及他使用初始化数据。dp[1][1] =1 还是dp[1][1] =0, 还需要再讨论。