题目描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入一行3个整数，用空格分开：n m k (1< =n,m< =50, 1< =k< =12)
接下来有 n 行数据，每行有 m 个整数 Ci (0< =Ci< =12)代表这个格子上的宝物的价值
本题如果直接使用 dfs 暴力搜索，将无法通过测试，但引入记忆化将可以剪枝避免大量的重复计算。我们知道如果一个问题可以分解为多个小问题，且各个小问题之间相互独立，那么我们可以使用动态规划来处理。
1.首先 定义 dp 数组：
dp[i][j][k][c]: 表示从 ((1, 1))走到 ((i,j))时，手里有 (k) 件宝贝，且宝贝价值的最大值为 (c) 时的行动方案数。
2.找到 状态转移方程：
根据题目知，小明只能向下或者向右行走，则((i,j)) 的状态应从 ((i-1,j)) 和 ((i,j-1)) 的状态转移过来，有 (dp[i][j]=dp[i-1][j]\quad OP \quad dp[i][j-1])，（ OP 表示某个操作）。
又知走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿），假设 当前格子中宝贝的价值为 cur 则：
若此时拿走宝贝：(dp[i][j][k][cur]+=dp[i-1][j][k-1][0…cur-1]+dp[i][j-1][k-1][0…cur-1])
// 拿走宝贝
for (int c = 0; c < cur; c++) {
dp[i][j][k][cur] += dp[i - 1][j][k - 1][c] + dp[i][j - 1][k - 1][c];
}
若不拿走宝贝：(dp[i][j][k][c]+=dp[i-1][j][k][c]+dp[i][j-1][k][c]), (c = 0, 1, 2 … 12)
// 不拿走宝贝
for (int c = 0; c
- base case
设 ((i,j)) 处宝贝的价值 (a[i][j]) 为当 k = 1时，(dp[i][j][1][a[i][j]]) 表示只选择当前宝贝，可知方案数即为从 ((1, 1))走到 ((i,j)) 的方案数。
定义 (DP[i][j]) 表示从 ((1, 1))走到 ((i,j)) 的方案数，易知 (DP[i][j] = DP[i – 1][j] + DP[i][j-1])，
则有 (dp[i][j][1][a[i][j]]+=dp[i-1][j][1][a[i-1][j]]+dp[i][j-1][1][a[i][j-1]])
// base case
dp[1][1][1][a[1][1]] = 1;
for (int i = 1; i
代码：
import java.util.Scanner;
public class Main {
static int MAXN = 50, MAXM = 50;
static int MAXK = 12, MAXC = 12;
static long[][][][] dp = new long[MAXN + 1][MAXM + 1][MAXK + 1][MAXC + 1];
static int[][] a = new int[MAXN + 1][MAXM + 1];
static int n, m, k, ans = 0, mod = 1000000007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
for (int i = 1; i
最大时间复杂度：(O(T)=O(ijkc)=O(50501213)=O(390000))
Original: https://www.cnblogs.com/Code-CHAN/p/14471491.html
Author: Code-CHAN
Title: 蓝桥杯 2014届真题 地宫取宝 动态规划解法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/714760/
转载文章受原作者版权保护。转载请注明原作者出处！