DFS进阶——地宫取宝

地宫取宝

题目分析（记忆化递归）

考虑一下dfs需要的参数，首先我每次可以向下和右两个方向走，其次对于当前的宝物我可以选择拿，也可以选择不拿，但是如果要拿一定有一个前提条件就是已经拿的宝物的最大价值小于当前宝物的价值，那么我需要知道已经拿的宝物的最大价值，所以每次dfs的时候都要传参这个最大价值。

接下来考虑dfs的过程，首先是终点判断，当我走到出口时说明递归该结束了，但是最终这个方案是否合法要取决于我当前拿到的宝物个数，所以宝物个数也是dfs的传参。代码如下。

if(x==n&&y==m) {
    if(num==k) return 1;
    return 0;
}

然后是dfs过程，我们要向两个方向遍历，并且通过拿的宝物的最大价值是否小于当前宝物的价值的判断来决定当前宝物是否可以拿。如果可以拿，那么要更新拿的宝物的最大价值为当前宝物的最大价值，并且拿到的宝物的数量也要加1。拿宝物还有一个前提就是当前宝物数量是小于k的，不然不需要拿。不拿宝物任何时候都可以不拿，所以不需要额外的判断。

for(int i = 0;i < 2;i++) {
    int nx = x + nextx[i];
    int ny = y + nexty[i];
    if(nx>n||ny>m) continue;
    if(value[nx][ny]>max&&num<k) res = (res + dfs(nx, ny, value[nx][ny], num+1))%mod;
    res = (res + dfs(nx, ny, max, num))%mod;
}

为了提高效率，我们采用记忆化递归，记录当前位置，当前最大值，当前宝物数量的状况下，继续遍历能够得到的方案数。

if(dp[x][y][max][num]!=-1) return dp[x][y][max][num];
long res = 0;
for(int i = 0;i < 2;i++) {
    int nx = x + nextx[i];
    int ny = y + nexty[i];
    if(nx>n||ny>m) continue;
    if(value[nx][ny]>max&&num<k) res = (res + dfs(nx, ny, value[nx][ny], num+1))%mod;
    res = (res + dfs(nx, ny, max, num))%mod;
}
dp[x][y][max][num] = res%mod;

但是这个题有一个易错点，如果当前最大值成为了数组下标，那么他就不可能为负数，初始化的时候只能初始化为0。但是我们的宝物价值有可能为0，如果最大值初始化为0，我们就拿不了价值为0的宝物。所以统一把宝物的价值都加1，让其最小值为0。

for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++) {
        value[i][j] = scanner.nextInt();
        value[i][j]++;
    }

在dfs的时候，当前位置的坐标的宝物我已经拿了，那么最初第一个位置1，1的宝物我可以拿也可以不拿，所以有两个dfs，主要要给这两个dfs的和进行取模，不然会错。

System.out.println((dfs(1,1,0,0)+dfs(1,1,value[1][1],1))%mod);

题目代码

import java.util.Arrays;
import java.util.Scanner;
public class Main{
	static int n,m,k;
	static int nextx[] = {0,1};
	static int nexty[] = {1,0};
	static int value[][];
	static long dp[][][][];
	static int mod = (int) (1e9+7);
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	n = scanner.nextInt();
	m = scanner.nextInt();
	k = scanner.nextInt();
	value = new int[n+1][m+1];
	dp = new long[n+1][m+1][14][k+1];
	for(int i = 0;i <= n;i++) {
		for(int j = 0;j <= m;j++) {
			for(int q = 0;q < 14;q++) {
				Arrays.fill(dp[i][j][q], -1);
			}
		}
	}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++) {
			value[i][j] = scanner.nextInt();
			value[i][j]++;
		}
	System.out.println((dfs(1,1,0,0)+dfs(1,1,value[1][1],1))%mod);
}
private static long dfs(int x, int y, int max, int num) {
	if(x==n&&y==m) {
		if(num==k) return 1;
		return 0;
	}
	if(dp[x][y][max][num]!=-1) return dp[x][y][max][num];
	long res = 0;
	for(int i = 0;i < 2;i++) {
		int nx = x + nextx[i];
		int ny = y + nexty[i];
		if(nx>n||ny>m) continue;
		if(value[nx][ny]>max&&num<k) res = (res + dfs(nx, ny, value[nx][ny], num+1))%mod;
		res = (res + dfs(nx, ny, max, num))%mod;
	}
	dp[x][y][max][num] = res%mod;
	return dp[x][y][max][num];
}
}