再探 地宫取宝

1490535525

题目描述
标题：地宫取宝

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

数据格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

例如，输入

2 2 2
1 2
2 1
输出
2
输入
2 3 2
1 2 3
2 1 5
输出
14
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

以前的题解 DFS记忆化搜索 http://www.xiaocp.com/single/36

当然，当时的通过率只有40%左右吧

来看看DP解法，100分通过，思路是这样的，我采用一个四维数组进行运算，即数组dp[x][y][k][max]，数组的意思是 走到坐标 x y已取到k件宝贝，宝贝最大值是max，数组的值是方法数，这么一来清晰明了多了，那么他当前的方法数 += x坐标减1 + y坐标减1 （因为是往下或者往右边走）

代码实现
public class Main{
static final int N = 55;
static final int M = 15;
static final int MOD = 1000000007;

static int dp[][][][] = new int[N][N][M][M];
static int map[][] = new int[N][N];

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int k = scanner.nextInt();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            map[i][j] = scanner.nextInt();
            map[i][j]++; // 区分本身为0
        }

    dp[1][1][1][map[1][1]] = 1;
    dp[1][1][0][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)
                continue;
            for (int c = 0; c <= k; c++)
                for (int max = 0; max < 13; max++) {
                    if (max < map[i][j])
                        dp[i][j][c + 1][map[i][j]] = ((dp[i][j][c + 1][map[i][j]]
                                % MOD + dp[i - 1][j][c][max] % MOD)
                                % MOD + dp[i][j - 1][c][max] % MOD)
                                % MOD;
                    dp[i][j][c][max] = ((dp[i][j][c][max] % MOD + dp[i - 1][j][c][max]
                            % MOD)
                            % MOD + dp[i][j - 1][c][max] % MOD)
                            % MOD;
                }
        }
    int ans = 0;
    // 结果是  最大宝贝价值  0 - 12 的总和
    for (int i = 0; i < 13; i++)
        ans = (ans + dp[n][m][k][i]) % MOD;

    System.out.println(ans);

    scanner.close();
}

}