題目描述
X 國(guó)王有一個(gè)地宮寶庫(kù)。是 n x m 個(gè)格子的矩陣。每個(gè)格子放一件寶貝。每個(gè)寶貝貼著價(jià)值標(biāo)簽。

地宮的入口在左上角，出口在右下角。

小明被帶到地宮的入口，國(guó)王要求他只能向右或向下行走。

走過(guò)某個(gè)格子時(shí)，如果那個(gè)格子中的寶貝價(jià)值比小明手中任意寶貝價(jià)值都大，小明就可以拿起它（當(dāng)然，也可以不拿）。

當(dāng)小明走到出口時(shí)，如果他手中的寶貝恰好是k件，則這些寶貝就可以送給小明。

請(qǐng)你幫小明算一算，在給定的局面下，他有多少種不同的行動(dòng)方案能獲得這k件寶貝。
輸入
輸入一行3個(gè)整數(shù)，用空格分開(kāi)：n m k (1< =n,m< =50, 1< =k< =12)

接下來(lái)有 n 行數(shù)據(jù)，每行有 m 個(gè)整數(shù) Ci (0< =Ci< =12)代表這個(gè)格子上的寶物的價(jià)值
輸出
要求輸出一個(gè)整數(shù)，表示正好取k個(gè)寶貝的行動(dòng)方案數(shù)。該數(shù)字可能很大，輸出它對(duì) 1000000007 取模的結(jié)果。
樣例輸入
2 3 2
1 2 3
2 1 5
樣例輸出
14
思路：像這種取模的操作，就考慮數(shù)學(xué)，dp，記憶化就可以了，一般逃不過(guò)這三種。
對(duì)于這個(gè)題目，我用的是記憶化搜索。dp[x][y][k][_max]代表的是走到坐標(biāo)(x,y)時(shí)，拿了k件寶物，最大值是_max的方案數(shù)，條件限制，每一個(gè)坐標(biāo)必須要考慮拿了多少件、最大值是多少這兩個(gè)因素。然后去搜索就可以了，如果遇到處理過(guò)的情況就直接返回就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define mod 1000000007 using namespace std;const int maxx=51; int a[maxx][maxx]; ll dp[maxx][maxx][maxx][15]; int n,m,k;inline int dfs(int x,int y,int num,int _max) {if(dp[x][y][num][_max+1]!=-1) return dp[x][y][num][_max+1];if(x==n&&y==m){if(num==k-1&&a[x][y]>_max) return dp[x][y][num+1][_max+1]=1;else if(num==k) return dp[x][y][num][_max+1]=1;return dp[x][y][num][_max+1]=0;}if(x<1||x>n||y<1||y>m) return 0;ll s=0;if(a[x][y]>_max){s+=dfs(x+1,y,num+1,a[x][y]);s+=dfs(x,y+1,num+1,a[x][y]);}s+=dfs(x+1,y,num,_max);s+=dfs(x,y+1,num,_max);return dp[x][y][num][_max+1]=s%mod; } int main() {scanf("%d%d%d",&n,&m,&k);memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);cout<<dfs(1,1,0,-1)<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2014年第五届真题]地宫取宝（记忆化搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。