dfs

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N = 55;
int g[N][N];
int dx[] = {0, 1}, dy[] = {1, 0};
int n, m, k, res;

void dfs(int x, int y, int item, int item_max)
{
    if (x == n && y == m)
    {
        if (item == k)
            res ++;
        return;
    }

    for (int i = 0; i <= 1; i ++)
    {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (1 <= new_x && new_x <= n && 1 <= new_y && new_y <= m)
        {
            if (item != k && g[new_x][new_y] > item_max)    // 剪枝一下 
                dfs(new_x, new_y, item + 1, g[new_x][new_y]);
            dfs(new_x, new_y, item, item_max);
        }
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)  cin >> g[i][j];
    dfs(1, 1, 0, -1);
    dfs(1, 1, 1, g[1][1]);
    cout << res << endl;
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>

using namespace std;
typedef long long LL;
const int N = 55, Mod = 1000000007;
int g[N][N];
LL f[N][N][15][13];    // 从(i, j)出发，已经持有cnt件物品，其中最大的物品价值为max_item，到终点的方案 
int dx[] = {0, 1}, dy[] = {1, 0};
int n, m, k;
LL res;

int dfs(int x, int y, int cnt, int max_item)
{
    if (f[x][y][cnt][max_item] != -1)  return f[x][y][cnt][max_item];

    f[x][y][cnt][max_item] = 0;
    if (x == n && y == m && cnt == k)
        return f[x][y][cnt][max_item] = 1;

    if (g[x][y] > max_item && cnt < k)
        f[x][y][cnt][max_item] = (f[x][y][cnt][max_item] + dfs(x, y, cnt + 1, g[x][y])) % Mod;

    for (int i = 0; i <= 1; i ++)
    {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (1 <= new_x && new_x <= n && 1 <= new_y && new_y <= m)
            f[x][y][cnt][max_item] = (f[x][y][cnt][max_item] + dfs(new_x, new_y, cnt, max_item)) % Mod; 
    }

    return f[x][y][cnt][max_item] % Mod;
}

int main()
{
    memset(f, -1, sizeof f);
    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] ++;    // 有些宝物是0，为了方便搜索，全部加1，总方案数不变
        }
    res = dfs(1, 1, 0, 0);
    cout << res % Mod << endl;
    return 0;
}