牛客 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

題目解析

這道題是走方格的更新版，但也不過就是加了個障礙而已，難度還是很簡單的，不過，這裡使用dfs遞歸會逾時，是以隻能轉而采用動态規劃思路實作。

1. 第一步：劃分子問題

   求解的是到（x，y）有多少條路徑，那麼在求解過程中一定需要知道到達（i，j）（i<=x,j<=y）有多少條路經，子問題很容易找到了吧。

2. 狀态轉移方程

   dp【i】【j】表示的是到（i，j）這個點有多少條路徑，沒什麼好解釋的，自然而然得出該結論

   dp【i+1】【j】=dp【i+1】【j】+dp【i】【j】

   表示的含義是：到達（i+1，j）點數目包括從下方這個點（i，j）的所有路徑

   dp【i】【j+1】=dp【i】【j+1】+dp【i】【j】

   表示的含義是：到達（i，j+1）點數目包括從左方這個點（i，j）的所有路徑

3. 填表

   為了最大程度節省空間，我們令障礙（i，j）的dp【i】【j】=-1，那麼當求解釋，遇到障礙直接跳過

   初始化：dp【i】【j】={0}

   到達（0，0）點隻有一條路徑，是以dp【0】【0】=1

   注意！一定令dp數組定義為long long型，因為數組幾乎成斐波那契數列這樣增長的，是以速度超快的

   接下來就是代碼實作

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
#include<limits.h>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

ll dp[31][31];
int n;

int main() {
	int x,y;
	while(scanf("%d%d%d",&x,&y,&n)!=EOF){
		memset(dp,0,sizeof(dp));
		int xt,yt;
		dp[0][0]=1;
		while(n--){
			scanf("%d%d",&xt,&yt);
			dp[xt][yt]=-1;
		}
		dp[0][0]=1;
		for(int i=0;i<=x;i++){
			for(int j=0;j<=y;j++){
				if(dp[i][j]==-1){
					continue;
				}
				if(j<y&&dp[i][j+1]!=-1){
					dp[i][j+1]+=dp[i][j];
				}
				if(i<x&&dp[i+1][j]!=-1){
					dp[i+1][j]+=dp[i][j];
				}
			}
		}
		printf("%lld\n",dp[x][y]); 
	} 

	return 0;
}