題目鏈接：http://121.42.142.123/JudgeOnline/problem.php?id=1227

題目描述

你是一只生活在籠子里的實驗室老鼠。實驗室是一個R行C列的格子矩陣(1 ≤ R,C ≤ 25). 每個格子是一個籠子. (尼瑪還要我活么……)為了讓你鍛煉身體，實驗室管理員允許你在籠子之間移動。你只能向右和向下移動。你不能斜著移動，也不能向上和向左移動。你所在的籠子是實驗室的左上角，標記為(1,1)。你想去右下角的籠子(R,C)里找你的女朋友(尼瑪老鼠也有女盆友么！！！)。但是有一些籠子是不能經過的，因為里面有貓（誰說老鼠怕貓么，還有，管理員有毛病么……）。你女朋友很愛數學，她想要知道有多少條不同的路徑可以從你的籠子到達她的籠子。寫一個程序來計算吧。（這樣的女朋友不要也罷……）

輸入

第一行包含2個整數R和C，第二行一個整數K，代表包含貓的籠子的個數，接下來K行包含K個不同的位置信息，代表K個包含貓的籠子的位置信息，注意(1,1)和(R,C)這兩個位置是不會有貓的， 否則出題者就沒法活了……

輸出

輸出一個非負整數代表你可以去你女朋友籠子里和她啪啪啪的路徑數目，你可以假設這個輸出會嚴格小于1,000,000,000。

樣例輸入

2 3 1 2 1

樣例輸出

2
思路：簡單dp，當前步數等于上一步可走兩條路徑的和即：f[i][j]=f[i-1][j]+f[i][j-1]; 代碼如下：
#include<string.h> #include<stdio.h> #define M 30int flag[M][M],f[M][M]; int r,c,k,a,b;int main(){ while(scanf("%d%d",&r,&c)!=EOF){scanf("%d",&k);for(int i=1;i<=k;++i){scanf("%d%d",&a,&b);flag[a][b]=1;}for(int i=1; i<=r; ++i){if(flag[i][1]==0) f[i][1]=1;else break;}for(int j=1; j<=c; ++j){if(flag[1][j]==0) f[1][j]=1;else break;}for(int i=2; i<=r; ++i)for(int j=2; j<=c; ++j){if(flag[i][j]==0)f[i][j]=f[i-1][j]+f[i][j-1];//只是向右方，下方走，那么走到該點的步數就是上左兩點的步數之和 }printf("%d\n",f[r][c]); } return 0; }

總結

以上是生活随笔為你收集整理的老鼠的求爱之旅 (DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。