蓝桥杯 2014届真题 地宫取宝 动态规划解法

题目描述

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 <= 12; c++) {
    dp[i][j][k][c] += dp[i - 1][j][k][c] + dp[i][j - 1][k][c];
}

3.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 <= n; i++) {
    for (int j = 1; j <= m; j++) {
        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]];
    }
}

代码：

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 <= n; i++)
            for (int j = 1; j <= m; j++)
                a[i][j] = sc.nextInt();
        
        // base case
        dp[1][1][1][a[1][1]] = 1;
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= m; j++)
                if (!(i == 1 && 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]];
                    dp[i][j][1][a[i][j]] %= mod;
                }
        
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
        		for (int l = 1; l <= k; l++) {
                    int cur = a[i][j];
                    // 拿走宝贝
                    for (int c = 0; c < cur; c++) {
                        dp[i][j][l][cur] += dp[i-1][j][l-1][c] + dp[i][j-1][l-1][c];
                        dp[i][j][l][cur] %= mod;
                    }
                    // 不拿走宝贝
                    for (int c = 0; c <= MAXC; c++) {
                        dp[i][j][l][c] += dp[i-1][j][l][c] + dp[i][j-1][l][c];
                        dp[i][j][l][c] %= mod;
                    }
                }
        
        for (int c = 0; c <= MAXC; c++) {
            ans += dp[n][m][k][c];
            ans %= mod;
        }
        
        System.out.println(ans);
    }
}

最大时间复杂度：\(O(T)=O(i*j*k*c)=O(50*50*12*13)=O(390000)\)