地宫取宝

原题地址：8.地宫取宝 - 蓝桥云课 (lanqiao.cn)

题目描述

X 国王有一个地宫宝库。是 n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入描述

输入一行 3 个整数，用空格分开：n, m, k(1≤ n, m≤50,1≤ k ≤12)n,m,k (1≤n,m≤50,1≤k≤12)。

接下来有 n 行数据，每行有 m 个整数 Ci​ (0≤Ci​≤12) 代表这个格子上的宝物的价值。

输出描述

要求输出一个整数，表示正好取 k 个宝贝的行动方案数。该数字可能很大，输出它对 109+7109+7 取模的结果。

输入输出样例

输入：

2 2 2

1 2

2 1

输出：

2

代码实现

#include<bits/stdc++.h>

using namespace std;
int n,m,k;
int a[55][55];//输入所给数组值所分配的内存空间
int dp[55][55][15][15];//开创记忆化的存储空间
//因为只进行向下走和向右走，所有写成这个样子，不明白的可以在了解以下笛卡尔积，向下是x轴，向右是y轴(一般情况下)
int dx[]={1,0};
int dy[]={0,1};
int p=1e9+7;//索取余数
//dfs()里面写x,y,mx,cnt分别代表更新的坐标，最大值，宝物数目
long long dfs(int x,int y,int mx,int cnt){
    if(x==n&&y==m)  return cnt==k;//这个是结束临界条件，到最后结束跳出
    if(dp[x][y][mx][cnt]!=-1)   return dp[x][y][mx][cnt];//进行记忆化搜索的地方，如果之前保存过这个值就不用再次计算而是直接使用保存过的值(值不会因为后续深搜改变的改变而是不变)
    long long res=0;//后续进行记忆化存储的给予赋值
    for(int i=0;i<2;i++){
    //进行向下或者向右的搜索
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1||ny<1||nx>n||ny>m)continue;
   //拿这个东西
        if(a[nx][ny]>mx&&cnt<k) res=(res+dfs(nx,ny,a[nx][ny],cnt+1))%p;
   //不拿这个东西
        res=(res+dfs(nx,ny,mx,cnt))%p;
    }
   //进行记忆化搜索的重要部分
    return dp[x][y][mx][cnt]=res;
}


int main(){
   //将dp数组置为-1，不置为0是因为宝物价值可能为0出现异议
    memset(dp,-1,sizeof dp);
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]++;//宝物的价值可以为0，++是为了防止宝物价值为0的情况，所有宝物价值都+1就是为了避免价值0的情况。你造一个数据，如果存在价值为0的物品就会少路径答案，如果不存在价值为0的情况，那这个a[i][j]++有没有都行
   //这里的++是为了让宝物价值最小也为1，问题问的是路线情况，并不用担心价值问题
        }
   //对一开始的宝物拿和不拿都进行深搜获得最终答案         
    cout<<(dfs(1,1,0,0)+dfs(1,1,a[1][1],1))%p<<endl;


    return 0;
}