动态规划 Shopee的办公室（二）

动态规划 Shopee的办公室（二）

题目描述

题目来源：

shopee的办公室非常大，小虾同学的位置坐落在右上角，而大门却在左下角，可以把所有位置抽象为一个网格（门口的坐标为0，0），小虾同学很聪明，每次只向上，或者向右走，因为这样最容易接近目的地，但是小虾同学不想让自己的boss们看到自己经常在他们面前出没，或者迟到被发现。他决定研究一下如果他不通过boss们的位置，他可以有多少种走法？

输入描述:

第一行 x,y,n (0<x<=30, 0<y<=30, 0<=n<= 20) 表示x,y小虾的座位坐标,n 表示boss的数量（ n <= 20）

接下来有n行, 表示boss们的坐标(0<xi<= x, 0<yi<=y，不会和小虾位置重合)

x1, y1

x2, y2

……

xn, yn

输出描述:

输出小虾有多少种走法

• 示例1

输入

3 3 2
1 1
2 2

输出

4

解题思路

• 用动态规划来解，创建一个与网格相同大小的数组，里面存储走到每个格子有多少条路径，遇到不能走的位置就把该位置的路径数置0，不能用递归，因为递归的话很多格子会重复进入，递归层数太多，复杂度太高，无法通过。用迭代的话就每一行扫描过去，每个格子的路径数就是其左边和下面格子中的数字之和（因为每个格子只能由左边或者下面进来，可以先把首行和首列进行初始化，均为1，遇到boss就停止，因为boss后面去不了，因此都是0）。

代码

• C++

#include<iostream>
#include<cstring>
 
using namespace std;
 
int main() {
    int spx, spy, bossn;
    cin >> spx >> spy >> bossn;
     
    char isBoss[spx+1][spy+1];
    memset(isBoss, 0, sizeof(isBoss));
    for(int i=0; i<bossn; i++) {
        int bossX, bossY;
        cin >> bossX >> bossY;
        isBoss[bossX][bossY] = 1;
    }
    long long pathNum[spx+1][spy+1];
    memset(pathNum, 0, sizeof(pathNum));
    // 先把首行和首列的值填上，如果遇到boss则后面的格子都去不了
    for(int i=0; i<=spx && !isBoss[i][0]; i++) pathNum[i][0]=1;
    for(int j=1; j<=spy && !isBoss[0][j]; j++) pathNum[0][j]=1;
    for(int i=1; i<=spx; i++){
        for(int j=1; j<=spy; j++){
            pathNum[i][j] = isBoss[i][j] ? 0 : pathNum[i-1][j]+pathNum[i][j-1];
        }
    }
    cout << pathNum[spx][spy] << endl;;
    return 0;
}