【牛客網】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

動态規劃，類似楊輝三角做法

#include<iostream>
using namespace std;
 
int main() {
    int x, y, n;
    cin >> x >> y >> n;
    long long int dp[30 + 1][30 + 1] = {0};
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        dp[x][y] = -1;
    }
    for (int i = 0;i <= x;i ++) dp[i][0] = 1;
    for (int j = 0;j <= y;j ++) dp[0][j] = 1;
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            if (dp[i][j] == -1) continue;
            if (dp[i - 1][j] != -1) dp[i][j] += dp[i - 1][j];
            if (dp[i][j - 1] != -1) dp[i][j] += dp[i][j - 1];
        }
    }
    cout << dp[x][y] << endl;
    return 0;
}