題目：

這是一個簡單的生存游戲，你控制一個機器人從一個棋盤的起始點(1,1)走到棋盤的終點(n,m)。游戲的規則描述如下：
1.機器人一開始在棋盤的起始點并有起始點所標有的能量。
2.機器人只能向右或者向下走，并且每走一步消耗一單位能量。
3.機器人不能在原地停留。
4.當機器人選擇了一條可行路徑后，當他走到這條路徑的終點時，他將只有終點所標記的能量。

如上圖，機器人一開始在(1,1)點，并擁有4單位能量，藍色方塊表示他所能到達的點，如果他在這次路徑選擇中選擇的終點是(2,4)

點，當他到達(2,4)點時將擁有1單位的能量，并開始下一次路徑選擇，直到到達(6,6)點。
我們的問題是機器人有多少種方式從起點走到終點。這可能是一個很大的數，輸出的結果對10000取模。

Input

第一行輸入一個整數T,表示數據的組數。
對于每一組數據第一行輸入兩個整數n,m(1 <= n,m <= 100)。表示棋盤的大小。接下來輸入n行,每行m個整數e(0 <= e < 20)。

Output

對于每一組數據輸出方式總數對10000取模的結果.

Sample Input

1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2

Sample Output

3948

分析：

要求到達（n,m)點有多少種方式，且有限制，第一個我會相到直接dfs，但是會發現復雜度過高，肯定會超時，所以記憶化搜索降低復雜度，表示每次到達某點存在多少種情況（通過迭代達成）。

AC代碼

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int M=1e3+10; int m,n,a[M][M],dp[M][M]; int dfs(int x,int y) {if(dp[x][y]!=-1)return dp[x][y];dp[x][y]=0;int ans=0;for(int i=0; i<=a[x][y]; i++)for(int j=0; j<=a[x][y]-i; j++){int u=x+i;int v=y+j;if(u<=0||v<=0||u>m||v>n)continue;ans=(ans+dfs(u,v))%10000;}dp[x][y]=ans;return ans; } int main() {int t;scanf("%d",&t);while(t--){memset(dp,-1,sizeof(dp));scanf("%d%d",&m,&n);for(int i=1; i<=m; i++)for(int j=1; j<=n; j++)scanf("%d",&a[i][j]);dp[m][n]=1;printf("%d\n",dfs(1,1));}return 0; }

總結

以上是生活随笔為你收集整理的How many ways HDU - 1978（记忆化搜索关于求多少种方式模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

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