蓝桥杯历届试题-地宫取宝 （C++代码） &记忆搜索

解题思路:
记忆化搜索，用visit[x][y][num][max]四维数组储存状态，在x,y位置上，并且手上有num个宝物，宝物最大值为max的状态下到终点的路径数为visit[x][y][num][max]



注意事项:宝物价值可能为0，因此main函数里max初始化为-1，并且dfs函数里面用max+1代替max，使得不会因为max = -1而使数组无效





参考代码:

#include<iostream>                                                                     
#include<cstring>                                                   
#define N 1000000007                                              
using namespace std;
int map[50][50];
int visit[50][50][15][15];
int m, n, k;
int dfs(int, int, int, int);
int main() {
	int i, j;
	cin >> m >> n >> k;
	memset(visit, -1, sizeof(visit));
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, 0, 0, -1);
	cout << visit[0][0][0][0];
	return 0;
}
int dfs(int x, int y, int num, int max) {
	if (visit[x][y][num][max+1] != -1) {
		return visit[x][y][num][max+1];
	}
	if (x == m-1  && y == n-1) {
		if (k == num) {
			visit[x][y][num][max+1] = 1;
			return visit[x][y][num][max+1];
		}
		else if (k == num + 1 && map[x][y] > max) {
			visit[x][y][num+1][map[x][y]] = 1;
			return visit[x][y][num+1][map[x][y]];
		}
		else return  visit[x][y][num][max+1] = 0;
	}
	long long s = 0;
	if (x < m-1 ) {
		if (map[x][y] > max) {
			s += dfs(x + 1, y, num + 1, map[x][y]);
			s %= N;
		}
		s += dfs(x + 1, y, num, max);
		s %= N;
	}
	if (y < n-1 ) {
		if (map[x][y] > max) {
			s += dfs(x, y + 1, num + 1, map[x][y]);
			s %= N;
		}
		s += dfs(x, y + 1, num, max);
		s %= N;
	}
	return visit[x][y][num][max+1] = s % N;
}