原题链接 https://www.acwing.com/problem/content/1214/

题目描述

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

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

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

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

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

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

输入格式

第一行 3 个整数，$n,m,k$，含义见题目描述。

接下来 $n$ 行，每行有 $m$ 个整数 $Ci $用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。

该数字可能很大，输出它对 1000000007 取模的结果。

数据范围

$1≤n,m≤50$,
$1≤k≤12$,
$0≤Ci≤12$

输入样例1：

2 2 2
1 2
2 1

输出样例1：

2

输入样例2：

2 3 2
1 2 3
2 1 5

输出样例2：

14

一、动态规划

1.状态表示与属性：用到动态规划的话就看题目中的条件：在某个位置、手中的物品总数；然后在每一步再把当前手中的最大价值记录。即形成了动态规划的“状态表示”：状态属性是数量，$dp[i][j][cnt][v]$表示在坐标为(i,j)时手中物品数量为cnt且最大价值为v的方案数量

2.状态计算：因为每一步的方案数量都是上面的一步或者左面一步的和;再其次，每一步都可以取或者不取当前的物品;
因此状态计算：当前的状态方案$dp[i][j][cnt][v]$=“上一步、不取当前物品”方案数量+“上一步、取当前物品”方案数量+“左一步、不取当前物品”方案数量+“左一步、取当前物品”方案数量。
不取好判断，取的话那么其上一步的最大值就需要循环判断。

3.注意事项：因为题里面物品的价值可以是0，因此在初始的时候，表示手中没拿物品的时候就设为-1，而下标不能是负数，因此输入每一个位置的物品价值的时候需要++，0就表示了手中没有物品。

4.因此整体的步骤就是：输入数据、赋初值、
循环枚举每个位置的方案数量[循环位置、循环手中物品数量、循环当前手中的物品最大值、取（循环上一步的最大值）+不取]。

5.在最后循环手中最后一个物品的价值的方案数量并相加。因为在最后一个位置其坐标、手中物品数量都是确定的，只是在最后手中的最大的物品价值是不确定的。🎅

#include<iostream>
using namespace std;

int n;//矩阵的行数
int m;//矩阵的列数
int k;//最后手中需要的物品数量
int a[55][55];//存放每个位置的物品价值
int dp[55][55][13][14];//前两维表位置，第三维表示手中的物品数量、第四维表示当前手中的物品最大值，整体值表示count方案数
int MOD=1000000007;
long long res;//存放最后的结果数

int main()
{
    //1.输入数据
    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]++;//++就是将每一位价值+1，0就可以表示手中什么也没有了
        }

    //2.赋初值
    dp[1][1][0][0]=1;//在第一步手中什么也没拿、价值为0的方案数量
    dp[1][1][1][a[1][1]]=1;//在第一步拿了第一件、并且手中的物品价值最大值自然就成了第一件的价值

    //3.开始枚举
    for(int i=1;i<=n;i++)//循环位置
        for(int j=1;j<=m;j++)
            {
                if(i==1&&j==1)//若是第一步的退出就行了，因为已经赋初值了
                    continue;
                for(int cnt=0;cnt<=k;cnt++)//循环手中物品的数量
                    for(int v=0;v<=13;v++)
                    {
                        //不取当前物品
                        dp[i][j][cnt][v]=(dp[i][j][cnt][v]+dp[i-1][j][cnt][v])%MOD;
                        dp[i][j][cnt][v]=(dp[i][j][cnt][v]+dp[i][j-1][cnt][v])%MOD;


                        //取当前物品
                        //若取的话:当前循环到的物品价值一定等于此处位置的物品价值,且手中的物品总数量一定大于0
                        if(v==a[i][j]&&cnt>0)
                        {
                          //循环上一步/左一步 的物品的最大值
                           for(int q=0;q<a[i][j];q++)
                           {
                                dp[i][j][cnt][v]=(dp[i][j][cnt][v]+dp[i-1][j][cnt-1][q])%MOD;
                                dp[i][j][cnt][v]=(dp[i][j][cnt][v]+dp[i][j-1][cnt-1][q])%MOD;
                            }
                        }
                    }
            }

    //4.循环取得总方案数量，因为在最后一个位置其坐标、手中物品数量都是确定的，只是在最后手中的最大的物品价值是不确定的
    for(int i=1;i<=13;i++)
        res=(res+dp[n][m][k][i])%MOD;

    //5.输出最后的结果
    cout<<res<<endl;

    return 0;
}

二、深度搜索

从第一步开始搜索，每步的数据是坐标位置、手中物品数量、当前物品价值的最大值，因此dfs函数有四个参数

1.terminator是“越界”以及“（到最后一步了且当且手中的物品的数量恰等于k）或者（手中物品等于k-1且当前位置的物品价值大于前面所有的有的物品价值）”

2.每一步先判断当前的物品价值是否大于前面所有的物品价值最大值：
①若小于，则当前的方案数量=“下一步”＋“右一步”；
②若大于，则当前的方案数量=“下一步且不取当前位置的物品”+“右一步且不取当前位置的物品”+“下一步且取当前位置的物品”+“右一步且取当前位置的物品”

3.因此总结最后的步骤：
(1)输入数据
(2)从位置为(1,1)且手中物品数量为1且最大值为-1开始搜索(-1即第一处什么也不选)
①terminator是越界以及最后的条件判断
②首先判断当前位置的物品价值是否大与之前的手中的物品最大值
③小于则搜索下一步以及右一步
④大于则搜索“取的下一步”+“取的右一步”+“不取的下一步”+“不取的右一步”
(3)输出结果

但是这个方法会超时！！！

#include<iostream>
using namespace std;

const int MOD=1000000007  ;
int n;//矩阵的行数
int m;//矩阵的列数
int k;//手中最后的物品数量
int a[55][55];//存放每一个位置的物品的价值
int res;//存放最后的结果

int dfs(int x,int y,int cnt,int v)
{
    //terminator
    //①越界
    if(x>n||y>m||cnt>k)
        return 0;
    //②到达终点
    if(x==n&&y==m)
        {
            if(cnt==k||(cnt==k-1&&a[x][y]>v))  //若在最后手中数量等于k，
                return 1;                       //或者最后手中数量等于k-1且最后的物品价值大于前面所有的物品价值的最大值                                             //(意思可以拿最后一件)
            else                                //（意思可以拿最后一件，拿了正好手中物品数量等于k）
                return 0;
        }

    //搜索
    if(a[x][y]>v)
    {
        return dfs(x+1,y,cnt,v)/*不取、去下一步*/+dfs(x,y+1,cnt,v)/*不取、去右一步*/
            +dfs(x+1,y,cnt+1,a[x][y])/*取、去下一步*/+dfs(x,y+1,cnt+1,a[x][y])/*取、去右一步*/;
    }
    else
        return dfs(x+1,y,cnt,v)+dfs(x,y+1,cnt,v);//搜索下一步以及右一步
}
int main()
{
    //1.输入数据
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];

    //2.进行搜索
    dfs(1,1,0,-1);//表示从(1,1)开始，手中没有物品且价值为-1（后面的dfs中有判断第一件拿或不拿的方案）

    //3.输出结果
    res=dfs(1,1,0,-1)%MOD;
    cout<<res<<endl;


    return 0;
}