题目：地宫取宝（蓝桥OJ 0216）

问题描述：

解题思路：

        本题思路和下方题目链接类似，都是典型的dfs模板问题。题目：混沌之地（蓝桥OJ 3820）-CSDN博客文章浏览阅读90次，点赞2次，收藏3次。题目：混沌之地（蓝桥OJ 3820）https://blog.csdn.net/2203_75582171/article/details/136806754?spm=1001.2014.3001.5501

 题解：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9 + 7;
const int inf = 1e9, N = 55;

int n, m, k , c[N][N];  // c[][]:地图

int dx[] = {0, 1};
int dy[] = {1, 0};

int dp[N][N][15][15];  // 表示某位置何种情况下的最大方案数

bool inmp(int x, int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}

// dfs表示从(x,y)位置且手里宝物最大值为mx,宝物个数为cnt个处开始时有多少种方案
ll dfs(int x, int y, int mx, int cnt)  // mx：当前手里最大值 cnt：当前手里个数 
{
	if(x == n && y == m)return (ll)(cnt == k);  // 到出口判断是否为K个，(ll)强制类型转换

	if(dp[x][y][mx][cnt] != -1)return dp[x][y][mx][cnt];
	
	ll res = 0;  // 计种数
	 
	for(int i = 0; i <2; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		
		if(!inmp(nx, ny))continue;
		
        // 两种情况：当下一个大于手中最大值时选择拿与不拿
        // 1.拿
		if(c[nx][ny] > mx && cnt < k)res = res + dfs(nx, ny, c[nx][ny], cnt + 1) % p;
		// 2.不拿
		res = (res + dfs(nx, ny, mx, cnt)) % p;
	} 

	return dp[x][y][mx][cnt] = res; 
    // 这里不同于链接那题走不到出口，这里是返回除出口外层该的结果***
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof dp);
	cin >> n >> m >> k;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j<= m; j++)
		{
			cin >> c[i][j];
			c[i][j] ++;
		}
	cout << (dfs(1, 1, 0, 0) + dfs(1, 1, c[1][1], 1) ) % p  << '\n';  // 一开始可以选择拿与不拿，有两种情况
	return 0;
}

解题思路：dfs,记忆化