动态规划/DP

时间复杂度：$O(N \times M \times 13^3)$

Notes:

该题是背包问题和最长上升子序列问题的结合，即求到达 $(i, j)$ 点的方案数与沿路径所取物品单调递增，进而再转换为一个 DP 问题。

解法/思路:

$f[i][j][k][c]$：表示在 $(i, j)$ 位置，沿途路径取了 $k$ 个宝贝，其最大价值为 $c$ 的所有方案数。

因为只能向下或向右走，所以只可能由 $(i - 1, j)$ 和 $(i, j - 1)$ 转移过来，针对 $(i - 1, j)$ 、 $(i, j - 1)$ 每一类，可分为不取宝贝和取宝贝两种情况，接下来进行分类讨论。

1、不取：因与上一个状态的 $k$、$c$ 相同，则 $f[i][j][k][c] = f[i - 1][j][k][c] + f[i][j - 1][k][c]$。

2、可取：只有当前 $(i, j)$ 点的宝贝大于上一状态最后所取的宝贝 $c$ 时才可取，可取时的上一状态为 $f[i - 1][j][k - 1][c]$、 $f[i][j - 1][k - 1][c]$，其中 $w[i][j] > c$（$w[i][j]$ 为 $(i, j)$ 点宝贝的价值）。

因为上述的 $k$、$c$ 较小，故可直接枚举 $k$、$c$ 即可。

C++ 代码

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

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

int main()
{
    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];
        }
    }
    f[1][1][1][w[1][1]] = 1; // (1, 1) 取
    f[1][1][0][0] = 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 u = 0; u <= 12; ++u) { // 个数
                for (int v = 0; v <= 13; ++v) { // 最大价值
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;
                    val = (val + f[i][j - 1][u][v]) % MOD;
                    if (u > 0 && w[i][j] == v) { // w[i][j] == v 是满足递增关系（可取）
                        for (int c = 0; c < v; ++c) { // f[i - 1][j], f[i][j - 1] 其中 c < v 的集合
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= 13; ++i) res = (res + f[n][m][k][i]) % MOD;
    cout << res << endl;
    return 0;
}