递归搜索

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 55;
const int MOD = 1000000007;

int n, m, k;
int g[N][N];
int ans;
int maxC; 

void dfs(int x, int y, int cnt, int max)// 
{
    // 边界1. 1.1 走出矩阵，1.2 拿的物品大于k，1.3 拿的物品大于k且没法拿物品 
    if((x == n || y == m) || cnt > k || (max == maxC && cnt < k)) {
        return;
    }
    // 边界2. 2.1 走到出口，拿了k件物品，2.2 拿了k-1件物品，但是还能拿出口处(n,m)这件 
    if((x == n-1 && y == m-1) && (cnt == k || (cnt == k-1 && max < g[n-1][m-1]))) {
        ans++;
        ans = ans % MOD;
        return;
    }

    //不拿
    dfs(x+1, y, cnt, max); // 向右走 
    dfs(x, y+1, cnt, max); // 向下走 

    //拿
    if(max < g[x][y]) {
        dfs(x+1, y, cnt+1, g[x][y]); // 向右走, 更新拿的数量和最大值 
        dfs(x, y+1, cnt+1, g[x][y]); // 向下走，更新拿的数量和最大值 
    }
}

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

    dfs(0, 0, 0, -1);

    cout << ans << endl;

    return 0;
}

dp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55;
const int maxK = 13;
const int wLim = 14;
const int MOD = 1000000007;
int w[N][N];
int dp[N][N][maxK][wLim];
int n,m,k;

//dfs(int row, int col)

int main(int argc, char** argv) {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            cin >> w[i][j];
            w[i][j]++;
        }
    dp[1][1][1][w[1][1]] = 1; // 取第一个 
    dp[1][1][0][0] = 1;       // 不取第一个 
    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 maxw = 0; maxw < wLim; maxw++){
                    int tmp = 0;
                    // 不取(i,j)的情况 
                    tmp = (tmp + dp[i-1][j][cnt][maxw]) % MOD;
                    tmp = (tmp + dp[i][j-1][cnt][maxw]) % MOD;

                    // 取(i,j)的情况，当前cnt一定大于0， 且在所有的cnt,maxw中，(i,j)一定是w[i][j] ，
                    if(w[i][j] == maxw && cnt > 0){
                        for(int c = 0; c < w[i][j]; c++) {
                            tmp = (tmp + dp[i-1][j][cnt-1][c]) % MOD;
                            tmp = (tmp + dp[i][j-1][cnt-1][c]) % MOD;
                        }
                    }
                    dp[i][j][cnt][maxw] = tmp;
                }
            }
        }
    }
    int res = 0;
    for(int i = 1; i < wLim; i++){
        res = (res + dp[n][m][k][i]) % MOD;
    }
    cout << res;
    return 0;
}