题目描述

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

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

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

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

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

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

样例

输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14

算法

记忆化搜索+动态规划

算法分析及总计

这个题还是有一定难度的，首先对于我来说（大佬别理我>…<）,卡了我一下的时间，也总算搞明白，在这里分享一下对这个题目的理解和知识点的理解。

大致读完题目后dp和搜索这两个思路容易得出，我们可以对比动态规划模板题目背包问题，在背包问题中，我们对于第几个物品有选择和不选择两种情况，这个题目有类似的描述，就是每个格子中的宝贝拿或者不拿（有条件限制，格子中的宝贝价值>=当前手中的宝贝价值最大值），那么我们怎么去解决背包问题呢，我们采用了二维数组来去表示对于第i个物品的不同体积的最大价值，然后通过递推来从局部最优解推出所有物品放入背包的最优解。我们来回到这个问题，类似，我们也可以开一个二维数组dp[sum][value]来表示当前有的宝贝数量中价值最大为value的方案数（最终目的求方案数，所以我们就递推它）。但想到这里就感觉后面不知道怎么办了（对于萌新的我来说hhhhhh）,如果仅开一个二维数组是无法保存具体状态的，我举个例子，dp[4][5]=3表示当前宝贝数量为3最大价值为5的方案数有三种，但对于这个地宫来说，有很多的点都可以代表这个状态，（1,1），（2,2）.....很多很多，那我们怎么办（好慌）。

防止视觉疲劳，我重新开一段hhhh，我们开一个四维数组就可以了，一听到四维数组下了一跳，这是个什么东东hhhh，大家不要纠结n维数组，我们这么去想，每一维都代表这一个状态，我们还回到背包问题，dp[i][j] i表示对于第几个物品，j表示体积大小，我们不难发现i和j其实就是两种状态，同样，dp[x][y][sum][value]就代表了4个状态，x当前横坐标，y纵坐标，sum当前拥有物品个数，value拥有物品中价值最大是多少。还是很好理解的。

这第一个问题就解决了，我们来看如何解决记忆化搜索的问题，我们为什么要记忆化搜索，y总在前面写过递归搜索树，我们不难发现有很多重复的计算，我举个简单的例子fibonacci数列1,1,2,3,5,8....当我们计算5时2和3被计算了两次，计算3时2又被计算了一次，显然这是重复的计算，如果我们把2这个结果直接保存下来，这样之后的计算就不用再算了，这就是记忆化搜索，对于本题来说我们从一个格子的状态推到另外一个格子的状态的时候，我们就把当前的状态给记录下来，这样之后搜索就可以直接拿出来用，避免多余计算。

搜索不太明白的小伙伴要提前学一下递归，dfs和bfs（确实是个硬骨头，可能我太笨hhhh）。

之后就是一下细节问题了，代码注释大家仔细看下就明白了，啃了一下，这也许就是做题的乐趣吧hhhh。

C++ 代码

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
const int N=51;
const int MOD=1000000007;
int map[N][N]; //记录当前迷宫宝贝的价值
int n,m,k;
int dp[N][N][15][15];//状态记录，比如dp[3][4][5][6]表示对于（3,4）这个点拥有物品数量为5最大价值为6的方案数。

int dfs(int x,int y,int sum,int max){  //搜就完了
      if(dp[x][y][sum][max+1]!=-1) return dp[x][y][sum][max+1]; //记忆化，如果某种状态被记录过则直接拿去用，max+1我解释一下，我么将最初最大价值初始化为-1，但这显然是不正确的，最大价值最低就是0，注意0也是一种状态，我们可以将没有宝贝的格子看成是价值为0的宝贝！！！！

      int t=0;//方案数
      if(x==n-1&&y==m-1){ //走到终点
          if(map[x][y]>max){  //能选最后一个格子中的宝贝
              if(sum==k||sum==k-1) t++; //要么不选，要么选，选的话就要保证自己还能再选一个且只能再选一个
          }
          else if(k==sum) t++;//不能选也是一种方案
          return dp[x][y][sum][max+1]=t; //返回终点的方案数

      }

      if(x+1<n){ //向下走
          if(map[x][y]>max){ //选
              t+=dfs(x+1,y,sum+1,map[x][y]);
              t%=MOD;
          }

          t+=dfs(x+1,y,sum,max); //不选
          t%=MOD;
      }

      if(y+1<m){ //能向右走
          if(map[x][y]>max){ //选
              t+=dfs(x,y+1,sum+1,map[x][y]);
              t%=MOD;
          }

          t+=dfs(x,y+1,sum,max);//不选
          t%=MOD;
      }
      dp[x][y][sum][max+1]=t;//两种情况考虑完后记录当前状态方案数
      return dp[x][y][sum][max+1];

}


int main(){
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>map[i][j];
        }
    }

    memset(dp,-1,sizeof(dp));
    dp[0][0][0][0] = dfs(0,0,0,-1);
    cout<<dp[0][0][0][0]<<endl;
    return 0;
}

题解不易，如果有帮助留下小心心哦~~~
谢谢(^▽^)