蓝桥杯2014年第五届真题-地宫取宝-题解（Java代码）两种做法（dfs 记忆型递归 剪枝)+(dp动态规划)

DFS做法:

import java.util.Arrays;
import java.util.Scanner;

public class 地宫取宝 {

    public static int n, m, k;// 行，列,K个宝贝
    public static int[][] val;// 价值
    public static final int MOD = 1000000007;
    public static long[][][][] cach = new long[50][50][14][13];// 记忆数组

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();// 行
        m = sc.nextInt();// 列
        k = sc.nextInt();// k件宝贝
        val = new int[n][m];

        for (int i = 0; i < val.length; i++) {
            for (int j = 0; j < val[i].length; j++) {
                val[i][j] = sc.nextInt();
            }
        }
        // 初始化
        for (int i = 0; i < cach.length; i++) {
            for (int j = 0; j < cach[i].length; j++) {
                for (int k = 0; k < cach[i][j].length; k++) {
                    Arrays.fill(cach[i][j][k], -1);
                }
            }
        }

        System.out.println(dfs(0, 0, -1, 0));
    }

    /**
     * 
     * @param x
     *            横坐标
     * @param y
     *            纵坐标
     * @param max
     *            走过的路程中价值最大的一个宝贝
     * @param cnt
     *            拿到的宝贝数量
     * @return
     */
    public static long dfs(int x, int y, int max, int cnt) {
        // x == n || y == m 边界判断
        // cnt > k 剪枝 如果当前拿到的物品数量大于k件的话那么就不用继续拿下去了
        if (x == n || y == m || cnt > k) {
            return 0;
        }
        // 如果不等于-1说该值已经计算过
        if (cach[x][y][max + 1][cnt] != -1) {
            return cach[x][y][max + 1][cnt];
        }
        long ans = 0;
        // 到达终点的情况
        if (x == n - 1 && y == m - 1) {
            // cnt == k 表示刚好拿到了k件物品

            // (cnt + 1 == k && val[x][y] > max)
            // 因为现在还处于没有拿当前物品的情况 因此如果当前物品的价值大于之前所拿物品的最大价值那么cnt就要+1
            if (cnt == k || (cnt + 1 == k && val[x][y] > max)) {
                ans = (ans + 1) % MOD;
            }
            return ans;
        }
        int cur = val[x][y];// 当前物品的价值
        // 拿当前物品的情况
        if (cur > max) {
            // 向下走
            ans += dfs(x + 1, y, cur, cnt + 1);
            // 向右走
            ans += dfs(x, y + 1, cur, cnt + 1);
        }
        // 不拿当前物品的情况
        ans += dfs(x + 1, y, max, cnt);
        ans += dfs(x, y + 1, max, cnt);

        // 记录横坐标为x，纵坐标为y,值为max,拿的物品数量为cnt的情况
        cach[x][y][max + 1][cnt] = ans % MOD;
        return ans % MOD;
    }
}

dp做法:

注意： i为x轴，j为y轴，l为物品数量，z为价值  这里的每一个格子都代表在横坐标为i纵坐标为j物品数量为l价值为z的情况下的最大方案数

import java.util.Arrays;
import java.util.Scanner;

public class 地宫取宝_动规做法 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int K = sc.nextInt();
        final int MOD = 1000000007;
        int[][] val = new int[n + 1][m + 1];// 价值
        for (int i = 1; i < val.length; i++) {
            for (int j = 1; j < val[i].length; j++) {
                val[i][j] = sc.nextInt();
            }
        }
        long[][][][] dp = new long[50][50][13][13];// dp数组

        // i为横坐标
        for (int i = 1; i <= n; i++) {
            // j为纵坐标
            for (int j = 1; j <= m; j++) {
                // l为物品数量
                for (int l = 0; l <= K; l++) {
                    // z为最大价值
                    for (int z = 0; z < 13; z++) {
                        // 第一个格子
                        if (i == 1 && j == 1) {
                            // l == 0表示我没拿当前物品的情况
                            // l == 1表示我拿了当前物品的情况并且z > val[1][1]并且价值大于第一个格子的价值
                            // 就是说当
                            // 在第一行第一列
                            // 我没拿当前物品 那么方案数就只有1个
                            // 我拿当前物品并且当前物品的价值要小于z（不然放不下）
                            if (l == 0 || (l == 1 && z > val[1][1])) {
                                dp[i][j][l][z] = 1;
                            }
                            continue;
                        }
                        // a表示我拿了的情况
                        // b表示我没拿的情况
                        long a = 0, b = 0;
                        // 如果l！=0就表示最少拿了一个物品
                        // z > val[i][j]前物品并且当前物品的价值要小于z
                        if (l != 0 && z > val[i][j]) {
                            //因为只能向下走和向右走那么就只有两种情况
                            //从上面下来的，从左边过来的
                            //上面i-1,左边j-1
                            //l - 1表示物品数量少一个的情况
                            //当前物品的价值
                            a = dp[i - 1][j][l - 1][val[i][j]]+ dp[i][j - 1][l - 1][val[i][j]];

                        }
                        //不拿的情况
                        //也是两种情况从上面过来的，从左边过来的
                        //因为没有拿，那么l也不需要减一
                        b = dp[i - 1][j][l][z] + dp[i][j - 1][l][z];
                        dp[i][j][l][z] = (a + b) % MOD;
                    }
                }
            }
        }
        System.out.println(dp[n][m][K][12]);

    }
}