这道题有人说是比较难，那就来看看考试中如何去拿分吧（

• 暴力dfs即可
  此方法在考试中只能拿到$3/7$的分数，但是呢此方法是最容易最好想的方法，也比较容易去写

#include <bits/stdc++.h>

using namespace std;

const int N=55,mod=1000000007;
int n,m,k,ans;
int g[N][N];
int dx[2]={0,1},dy[2]={1,0};

void dfs(int x,int y,int num,int v)
{
    if(x==n&&y==m)
    {
        if(num==k)
            ans=(ans+1)%mod;
        return;
    }

    if(x==0&&y==0)
    {
        dfs(1,1,num,-1);
        dfs(1,1,num+1,g[1][1]);
    }

    for(int i=0;i<2;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>m)continue;

        dfs(a,b,num,v);

        if(g[a][b]>v)
            dfs(a,b,num+1,g[a][b]); 
    }
}

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

    dfs(0,0,0,-1);
    cout<<ans<<endl;
    return 0;
}

下面两种方法都是可以拿满分的：

• dp:此方法确实应该是比较难写出来的，不过也不算难，虽说状态转移方程有四维但都是常规的思路
  棋盘：对应两维：$i,j$, $k$选的数量，$v$最大价值。

#include <bits/stdc++.h>
using namespace std;
const int N=55,mod=1e9+7;
typedef long long LL;
int n,m,k,g[N][N],f[N][N][13][15];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>g[i][j];g[i][j]++;}

    f[1][1][0][0]=1;
    f[1][1][1][g[1][1]]=1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1)continue;
            for(int a=0;a<=k;a++)
                for(int b=0;b<=13;b++)
                {
                    f[i][j][a][b]=f[i-1][j][a][b];
                    f[i][j][a][b]=(LL)(f[i][j][a][b]+f[i][j-1][a][b])%mod;
                    if(a>0&&b==g[i][j])
                        for(int c=0;c<g[i][j];c++)
                        {
                            f[i][j][a][b]=(LL)(f[i][j][a][b]+f[i-1][j][a-1][c])%mod;
                            f[i][j][a][b]=(LL)(f[i][j][a][b]+f[i][j-1][a-1][c])%mod;
                        }
                }
        }
    LL res=0;
    for(int i=0;i<=13;i++)
        res=(res+f[n][m][k][i])%mod;
    cout<<res<<endl;
    return 0;
}

• 记忆化搜索
  其实记忆化搜素就是比dp可能好写一点，但是思路是一致的，所以一般在dp思路清楚，但难以实现时使用记忆化搜索，而且记忆化的顺序很容易想到，本题正好和dp相反

#include <bits/stdc++.h>

using namespace std;

const int N=55,mod=1000000007;
int n,m,k,ans;
int g[N][N];
int dx[2]={0,-1},dy[2]={-1,0};
int f[N][N][13][14]; 
int dp(int x,int y,int num,int v)
{
    if(x==1&&y==1&&num==0&&v==0)return 1;
    if(x==1&&y==1&&num==1&&v==g[1][1])return 1;
    if(f[x][y][num][v]!=-1)return f[x][y][num][v];
    int &C=f[x][y][num][v];
    C=0;
    for(int i=0;i<2;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>m)continue;
        C=(C+dp(a,b,num,v))%mod;
        if(v==g[x][y])
            for(int j=0;j<g[x][y];j++)
                C=(C+dp(a,b,num-1,j))%mod;
    }
    return C;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            g[i][j]++;
        }
    memset(f,-1,sizeof f);

    for(int i=0;i<=13;i++)
        ans=(ans+dp(n,m,k,i))%mod;
//      cout<<dp(n,m,k,i)<<endl;
    cout<<ans<<endl;
    return 0;
}