蓝桥杯2014年第五届真题-地宫取宝Java

参考代码:

import java.util.Scanner;

public class 地宫 {
   static int[][] arr;
   static int n;
   static int m;
   static int k;
   static long[][][][] dp = new long[50][50][14][12];

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       n = sc.nextInt();  //行
       m = sc.nextInt();   //列
       k = sc.nextInt(); //取多少个宝贝
       arr = new int[n][m];
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               arr[i][j] = sc.nextInt();
           }
       }
       intdp();
       //max不能为0  0=0可能会直接执行else
       long r = move(0, 0, -1, 0);
       System.out.println(r);
   }
   public static void intdp() {
       for (int i = 0; i < 50; i++) {
           for (int j = 0; j < 50; j++) {
               for (int l = 0; l < 14; l++) {
                   for (int o = 0; o < 12; o++) {
                       //初始化为-1
                       dp[i][j][l][o] = -1;
                   }
               }
           }
       }
   }
   //row:当前行，col当前列，max行走中的最大宝贝值，count拿的数量
   public static long move(int row, int col, int max, int count) {
       if (dp[row][col][max + 1][count] !=-1){
           return dp[row][col][max + 1][count];
       }
       long r = 0;
       if (row >= n || col >= m || count > k)  //走出了格子 或者拿多了宝贝
           return 0;
       //如果拿的数量=宝贝的数量或者.拿的数量=宝贝的数量-1.并且宝贝价值大可以拿起来

       if (row == n - 1 && col == m - 1) {   //到了右下角
           //如果拿的数量=宝贝的数量或者.拿的数量=宝贝的数量-1.并且宝贝价值大可以拿起来
           if (count == k || (count == k - 1 && arr[row][col] > max)) {
               return 1;
           }
           return 0;
       }
       // 走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
       if (arr[row][col] > max) {  //宝贝价值大
           r += move(row, col + 1, arr[row][col], count + 1);
           r += move(row, col + 1, max, count);   //右不拿
           r += move(row + 1, col, arr[row][col], count + 1);   //下拿
           r += move(row + 1, col, max, count);   //下不拿
       }
       //宝贝价值小
       else {
           r += move(row, col + 1, max, count);   //右不拿
           r += move(row + 1, col, max, count);   //下不拿
       }
       //保存起来
       dp[row][col][max + 1][count] = r % 1000000007;
       return r % 1000000007;
   }
}