地宫取宝 -- DP

解题思路:

dp[x][y][num][maxValue] 为走到坐标(x, y)时, 不同行走方案总数的最优值(最大值),
num为背包中的物品总数, maxValue为背包单个物品最大的价值。

此时未装入(x, y)处的物品。

注意事项:
注意dp数组的初始化问题，dp[1][1][k][]，在（1，1）的位置，有两种选择，

        不拿    dp[1][1][0][] = 1；

        拿        如果拿（1，1）的物品，此时第四维数据c >= C[i][j]+1（下标从0开始） 时才可以拿 这个物品 dp[1][1][1][c >= C[i][j]+1] = 1；

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 52;
const int maxnC = 13;
const int Q = 1e9+7;   
int dp[maxn][maxn][maxnC][maxnC];     // 动态规划 dp[x][y][num][maxValue]
int C[maxn][maxn];      // 物品价值
int N, M, K;
int solve(){       // 迭代地动态规划
    for (int i = 1; i <= N; i++)      // x 坐标
        for (int j = 1; j <= M; j++)  // y 坐标
            for (int k = 0; k <= K; k++)   // 背包内物品总数
                for (int c = 0; c < maxnC; c++){      // 背包内单个物品的最大价值
                    if (i == 1 && j == 1){
                        if (k == 0 || (k == 1 && c > C[i][j]))
                            dp[i][j][k][c] = 1;
                        continue;            // 当 i，j == 1，1 时，因为是第一件物品，k>1无任何意义，直接continue
                    }
                    int t1 = 0, t2 = 0;
                    // 装当前物品
                    if (k > 0 && C[i][j] < c)
                        t1 = (dp[i][j-1][k-1][C[i][j]] + dp[i-1][j][k-1][C[i][j]]) % Q;
                    // 不装当前物品
                    t2 = (dp[i][j-1][k][c] + dp[i-1][j][k][c]) % Q;
                    dp[i][j][k][c] = (t1 + t2) % Q;
                }
    return dp[N][M][K][maxnC-1];
}
int main(){
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> C[i][j];
    cout << solve();
    return 0;
}