AcWing 1212. 地宫取宝

Problem: AcWing 1212. 地宫取宝

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这是一个动态规划问题，我们需要找到所有可能的路径，其中每个路径中的宝物价值都是递增的，并且恰好有k个宝物。我们可以使用一个四维的动态规划数组dp[i][j][p][q]，其中i和j表示当前的位置，p表示当前手中宝物的数量，q表示当前手中宝物的最大价值。然后，我们可以使用深度优先搜索来遍历所有可能的路径。

解题方法

首先，我们初始化动态规划数组，然后遍历所有可能的位置、宝物数量和宝物最大价值。对于每个位置，如果宝物数量和宝物最大价值都为0，或者宝物数量为1且宝物最大价值等于当前位置的宝物价值，那么就有一种方案。然后，如果当前位置的行数大于1，那么可以从上面的位置走到当前位置，如果宝物最大价值大于等于当前位置的宝物价值，那么还可以选择当前位置的宝物。同样，如果当前位置的列数大于1，那么可以从左边的位置走到当前位置，如果宝物最大价值大于等于当前位置的宝物价值，那么还可以选择当前位置的宝物。最后，对于所有可能的宝物最大价值，将对应的方案数加到答案中。

复杂度

时间复杂度:

O ( n 2 ∗ k 2 ) O(n^2 * k^2) O(n2∗k2)，其中n是地宫的大小，k是需要收集的宝物数量。因为我们需要遍历所有可能的位置、宝物数量和宝物最大价值。

空间复杂度:

O(n^2 * k^2)，我们需要一个四维数组来存储动态规划的状态。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n, m, k;
	static int MAXN = 56, MAXK = 15;
	static int[][] arr = new int[MAXN][MAXN];
	static long MOD = 1000000007;
	static long[][][][] dp = new long[MAXN][MAXN][MAXK][MAXK];

	public static void main(String[] args) throws IOException {
		n = nextInt();
		m = nextInt();
		k = nextInt();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i][j] = nextInt();
			}
		}
		init();

		out.println(dfs(0, 0, 0, -1));
		out.flush();

	}

	private static void init() {
		// TODO Auto-generated method stub
		for (int i = 0; i < MAXN; i++) {
			for (int j = 0; j < MAXN; j++) {
				for (int k = 0; k < MAXK; k++) {
					for (int l = 0; l < MAXK; l++) {
						dp[i][j][k][l] = -1;
					}
				}
			}
		}

	}

	/**
	 * 
	 * @param x
	 * @param y
	 * @param num 当前已经收集宝物的个数
	 * @param max 当前收集宝物的最大值
	 * @return 为什么要有这个最大值？ 因为题目中强调 走过某个格子时，如果那个格子中的宝贝价值
	 *         比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
	 * 
	 */

	private static long dfs(int x, int y, int num, int max) {
		// TODO Auto-generated method stub
		if (dp[x][y][num][max + 1] != -1) {
			return dp[x][y][num][max + 1];
		}

		// 结束条件 : 到达终点
		if (x == n - 1 && y == m - 1) {
			// 1. 收集宝藏的数量等于k 或者 收集宝藏的数量为k-1但是最后一个位置
			// （也就是当前位置）大于之前收集到的宝藏的最大值 就可以加上当前这个满足k个
			if (num == k || (num == k - 1 && max < arr[n - 1][m - 1])) {
				// dp[x][y][num][max + 1] = 1;
				return 1;
			} else {
				// dp[x][y][num][max + 1] = 0;
				return 0;
			}
		}
		long s = 0;
		// 向下
		if (x + 1 < n) {
			// 判断当前数字可拿不可拿
			// 满足题意 可以拿走
			if (max < arr[x][y]) {
				s += dfs(x + 1, y, num + 1, arr[x][y]);
			}
			s += dfs(x + 1, y, num, max);
			s %= MOD;
		}

		if (y + 1 < m) {
			if (max < arr[x][y]) {
				s += dfs(x, y + 1, num + 1, arr[x][y]);
			}
			s += dfs(x, y + 1, num, max);
			s %= MOD;
		}

		dp[x][y][num][max + 1] = s;
		return dp[x][y][num][max + 1];

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}