题解 P1176 【路径计数2】

· · 题解

一道基础的动态规划题目

首先，题目描述的重点在于每次只能移动到下方相邻的格子或者右方相邻的格子，所以，我们就可以得出结论：到达第n个格子的路径数量是这个格子左边的格子的路径数量+上边格子的路径数量。我们定义一个DP数组，DP[i][j]（也就是状态）代表第M[i][j]个格子的路径数量，根据上面的推论，我们可以得出状态转移方程：DP[i][j] = DP[i-1][j]+DP[i][j-1];

然而之后我们会发现，我们还没有对题目中的障碍进行处理。对于障碍的处理其实是非常简单的。遇见障碍，这条路就走不通了，也就是不对这个格子进行计算。那么如何做到不对该格子进行计算呢？有两种解决方法。

第一种：

当障碍数量小的时候，这时候我们就可以把所有障碍的路径记录一下，在动态规划的过程中进行处理，也就是当i = x and j = y的时候跳过循环，时间复杂度为O(mn^2)，记录障碍的空间复杂度为O(m)。

第二种：

当障碍数量大的时候，这时候我们就需要多花费一些空间了。其实我们可以把所有的障碍坐标映射到一个二维数组中，也就是构造一个Map，true表示无障碍，false表示有障碍。在输入障碍的时候将对应下标变成false。判断也就是当Map[i][j] = false的时候跳过循环。时间复杂度为O(n^2)，二维数组的空间复杂度为O(n^2)。

所以我们就用第二种方法，代码如下：

#include <bits/stdc++.h>//偷个懒 
using namespace std;
#define P 100003//膜数 
bool Map[1001][1001];//我们要构造的二维矩阵 
int DP[1001][1001],n,m;//DP数组，n为长度，m为障碍数 
int Max(int a,int b)
{
    return a>b?a:b;
}
int main(int argc,char ** argv)
{
    int i,j,x,y;
    ios::sync_with_stdio(false);//关闭IO同步，增快cin,cout速度 
    cin >> n >> m;//依次输入 
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= n;j++)
            Map[i][j]=true;
    }//个人习惯，把Map变为true 
    for(i = 0;i < m;i++)
    {
        cin >> x >> y;//输入 
        Map[x][y] = false;//把Map[x,y]变为false 
    } 
    for(i = 1;i <= n;i++)
    {
        if(Map[i][1] == false)
            break;
        DP[i][1] = 1;
    }//初始化状态 
    for(i = 1;i <= n;i++)
    {
        if(Map[1][i] == false)
            break;
        DP[1][i] = 1;
    }//初始化状态 
    for(i = 2;i <= n;i++)//从2开始循环 
    {
        for(j = 2;j <= n;j++)
        {
            if(Map[i][j] == false)//判断，如果为障碍，则不对该格子进行处理 
                continue;
            DP[i][j] = (DP[i-1][j]+DP[i][j-1])%P;//注意，这里要每步取模，不然会溢出 
        }
    }
    cout << DP[n][n] << endl;//输出最后的答案 

    return 0;
}