思路

因为太久没做dp题了，所以花了一个小时才ac，完全把记忆化搜索这回事忘了
我们定义一个四维$dp$的状态为$dp[i][j][k][l]$表示当前走到$(i,j)$，此时拥有$k$件物品，且$k$件物品的最大值不超过$l$的行动方案数
转移类型有：1. 获取当前位置的物品 2. 不获取
易得转移方程：
1. $dp[i][j][k][l] += \sum_{p=0}^{l-1} dp[i-1][j][k-1][p]+dp[i][j-1][k-1][p]，k>0$
2. $dp[i][j][k][l] += dp[i-1][j][k][l] + dp[i][j-1][k][l]$

很重要的一点是，为了防止数组访问越界，我们规定数组中的价值均大于0，因为枚举每一个物品时，我们是从当前物品的价值-1的位置递推的

#include<iostream>
#include<algorithm>
#include<cstring>
//dp[i][j][k][l]表示当前位置为(i, j)并已取得k件物品，且k件物品的最大价值不超过l的行动方案数
using namespace std;
long long dp[55][55][15][15];
int a[55][55];
const int mod = 1e9 + 7;
int main()
{
    int n, m, num, mx = 0;
    cin >> n >> m >> num;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            ++a[i][j];
            //保证数组里物品的大小不为0，否则dp时会出现越界访问
            mx = max(mx, a[i][j]);
        }
    }
    for (int i = 0; i <= mx; i++) dp[1][1][0][i] = 1;
    for (int i = a[1][1]; i <= mx; i++) {
        dp[1][1][1][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            for (int k = 0; k <= num; k++) {
                if (k > 0) {
                    for (int l = a[i][j]; l <= mx; l++) {
                        dp[i][j][k][l] = (dp[i][j][k][l] % mod + dp[i - 1][j][k - 1][a[i][j] - 1] % mod + dp[i][j - 1][k - 1][a[i][j] - 1] % mod) % mod;
                    }
                }
                for (int l = 0; l <= mx; l++) {
                    dp[i][j][k][l] = (dp[i][j][k][l] % mod + dp[i - 1][j][k][l] % mod + dp[i][j - 1][k][l] % mod) % mod;
                }
            }
        }
    }
    cout << dp[n][m][num][mx] % mod << endl;
    return 0;
}