Grid (基础DP)
题目:
给一个 H×W 的网格,网格由‘.’和‘#’组成,一开始在左上角 (1,1)(1,1) 每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角 (H,W) 有多少种走法。
其中 2<=H,W<=1000;
答案对 10^9+7 取模。
题目分析:
与洛谷的走方格题目类似,属于基础的DP问题,区别在于数据的范围
这题的数据比较大,所以要对1e9+7取模;
1.初始化,对于第一行和第一列,如果没遇到‘#’全部初始化为1,‘#’之后就不能走了也就是0
2.状态转移方程 ,由于从左上走到右下,也就是说当前状态只能由左边和上边得到:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
3.题目要求,若该点为‘#’ dp状态为0
坑点:
我们一般会在最终结果处对答案进行取模,然而,这题的数据量很大,如果不及时取模会导致出界:
所以我们每次更新dp[i][j]时就对其进行取模,就可以避免这个问题
AC代码:
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
ll dp[N][N];
char mp[N][N];
const int mod = 1e9 + 7;
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> mp[i][j];}}for (int i = 1; i <= m; i++){if (mp[1][i] == '#')break;else dp[1][i] = 1;}for (int j = 1; j <= n; j++){if (mp[j][1] == '#')break;else dp[j][1] = 1;}for (int i = 2; i <= n; i++){for (int j = 2; j <= m; j++){if (mp[i][j]=='#')dp[i][j] = 0;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];dp[i][j] %= mod;}}printf("%lld\\n", dp[n][m]);
}