记忆化搜索——地宫取宝

「爱情、让人受尽委屈。」 2022-08-21 01:10 111阅读 0赞

> 标题：地宫取宝

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

【数据格式】

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

输出它对 1000000007 取模的结果。

例如，输入：  
2 2 2  
1 2  
2 1  
程序应该输出：  
2

再例如，输入：  
2 3 2  
1 2 3  
2 1 5  
程序应该输出：  
14

再例如，输入：  
20 18 6  
0 7 2 3 9 1 11 9 7 11 6 9 11 6 10 8 11 6  
0 5 4 9 6 9 10 10 1 0 7 1 10 8 0 9 6 5  
4 10 10 9 1 9 6 2 4 1 0 6 4 7 3 7 10 7  
0 3 11 4 5 9 3 10 9 4 1 7 7 8 10 9 2 11  
10 1 4 5 5 10 1 7 6 0 11 5 10 3 3 6 3 5  
3 4 3 2 6 0 11 5 3 3 3 4 2 10 3 0 11 11  
6 3 5 8 10 9 6 3 5 0 3 7 7 11 6 6 3 6  
6 4 2 11 4 7 9 8 7 7 7 0 9 11 0 7 0 9  
7 2 9 11 2 6 0 10 5 11 4 7 8 0 6 3 3 10  
8 3 6 10 6 9 6 10 8 6 9 10 1 5 6 3 4 2  
1 5 9 2 3 6 11 10 5 2 7 10 1 8 11 8 6 0  
0 5 1 7 1 8 8 8 9 0 2 0 11 3 10 9 8 0  
9 10 0 8 6 2 8 8 4 6 7 2 11 0 4 3 7 9  
0 8 2 5 9 3 11 2 9 0 6 6 11 11 1 1 10 8  
4 6 0 2 1 8 6 4 7 5 5 2 0 2 5 10 1 6  
6 2 1 11 4 9 0 8 7 4 5 10 11 11 6 1 6 4  
7 3 10 3 10 10 10 6 9 9 11 7 0 9 11 0 1 5  
6 11 9 4 3 6 4 0 9 0 4 11 7 1 2 1 1 10  
6 1 4 5 9 9 7 3 3 7 11 2 10 6 8 6 3 4  
9 10 3 9 6 4 7 11 3 9 7 4 8 10 1 5 7 0  
输出：  
761196661

资源约定：  
峰值内存消耗 < 256M  
CPU消耗 < 1000ms

> 理解题意：  
> 1.每个格子都有宝物，只不过有的格子的宝物的价值为0。  
> 2.只有当某个格子的宝物的价值大于小明手中的最大价值的宝物时，小明才可以选择拿或不拿，注意是拿而不是换  
> 注意不拿有两种情形，一是不想拿（碰到一个更大价值的宝物，但选择不拿），而是不能拿（碰到的宝物的价值比小明当前手中宝物的最大值小）
> 
> 解题思路  
> 刚开始的时候是用“纯粹”的深搜做的，结果超时了，只过了40%  
> 然后在同学的启发下看到有大量的重复解，使用了记忆化搜索，AC
> 
> 记忆化搜索与动态规划：  
> 记忆化搜索在算法上依然是搜索的流程，在求解的时候按照自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以供后来重复使用，这就是记忆化的体现。所以在一开始，对记忆数组需要初始化一个标记值，用以区分之前是否已经遇到过了。在这道题中，rec数组初始化为-1。

import java.util.Scanner;
    
    public class Main {
    
        public final static int MOD = 1000000007;
        public static int N,M,K;
        public static int[][] maze = new int[60][60];
        public static long[][][][] rec = new long[60][60][15][15];
    
        public static void init(){
            for(int i=0;i<60;i++){
                for(int j=0;j<60;j++){
                    for(int k=0;k<15;k++){
                        for(int l=0;l<15;l++) rec[i][j][k][l] = -1;
                    }
                }
            }
        }
        public static void show(){
            System.out.println("maze output:");
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++) System.out.print(maze[i][j]+" ");
                System.out.println();
            }
        }
        public static long DFS(int x,int y,int k,int v){
            long ret = rec[x][y][k][v];
            if(ret!=-1){
       //在之前的搜索中已经得到了，直接返回即可
                return ret;**//记忆化搜索的体现**
            }
            ret = 0;
            //边界！！
            if(x==N-1&&y==M-1){
       //搜到出口了，但注意此处的宝物还没有决定是否去拿，所以还要根据情况讨论
                if(maze[x][y]>v){
       //可拿可不拿
                    if(k==K||k==K-1) ++ret;
                }
                else{
       //拿不了
                    if(k==K) ++ret;
                }
                return rec[x][y][k][v]=ret;
            }
            //还没有到达终点
            if(x+1<N){
       //可以往下走
                if(maze[x][y]>v){
       //可拿可不拿
                    ret += DFS(x+1, y, k+1, maze[x][y]);
                    ret %= MOD;
                }//不拿，与不能拿时写在一起
                ret += DFS(x+1, y, k, v);
                ret %= MOD;
            }
            if(y+1<M){
       //可以往右走
                if(maze[x][y]>v){
       //可拿可不拿
                    ret += DFS(x, y+1, k+1, maze[x][y]);
                    ret %= MOD;
                }
                ret += DFS(x, y+1, k, v);
                ret %= MOD;
            }
            //将结果记录在数组中
            return rec[x][y][k][v]=ret;
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                N = in.nextInt();
                M = in.nextInt();
                K = in.nextInt();
                init();
                for(int i=0;i<N;i++){
                    for(int j=0;j<M;j++){
                        maze[i][j] = in.nextInt();
                        //现在宝物的价值区间为[1,13]
                        ++maze[i][j];//因为输入的宝物价值可以为0，会与标记数组冲突，所以将其全部加1
                    }
                }
                long t1 = System.currentTimeMillis();
                //show();
                //注意最后一个参数设为-1，因为其含义是当前小明手中宝物的最大价值，是需要基于比较进行更新的，所以设其初值为-1
                //宝物价值为0，只要手中没有宝物也是可以拿的
                //从(0,0)点出发，在手中 没有宝物时的方案
                long ans = DFS(0, 0, 0, 0);
                System.out.println(ans);
                long t2 = System.currentTimeMillis();
                //System.out.println("time cost:"+(t2-t1));
            }
        }
    
    }