算法1

会超时

(暴力dfs搜索) $O(n!)$

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 56;

int mp[maxn][maxn];
int vis[maxn][maxn];
int dir[2][2] = {{0, 1}, {1, 0}};

int n, m, k;
int max_item;
int ans;

bool check1(int x, int y) // 判断是否有越界
{
    if (x > 0 && x <= n && y > 0 && y <= m)
        return true;
    else
        return false;
}


void dfs(int x, int y, int cnt, int max_item)
{
    if (x == n && y == m) //到了终点要返回
    {
        if (cnt == k) // 到了终点的时候，手中有k件物品，答案就加一
            ans = (ans + 1) % 1000000007;
        return;
    }
    else
    {
        for (int i = 0; i < 2; i++) // 向下或者向右
        {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (!vis[dx][dy] && check1(dx, dy))
            {
                // 拿这件物品
                if (cnt != k && mp[dx][dy] > max_item)
                {
                    vis[dx][dy] = 1;
                    dfs(dx, dy, cnt + 1, mp[dx][dy]);
                    vis[dx][dy] = 0;
                }
                // 不拿这件物品
                vis[dx][dy] = 1;
                dfs(dx, dy, cnt, max_item);
                vis[dx][dy] = 0;
            }
        }
    }
    return;
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &mp[i][j]);
        }
    }
    memset(vis, 0, sizeof(vis)); // 进去之后出来要刷新vis数组
    vis[1][1] = 1;
    dfs(1, 1, 1, mp[1][1]);
    vis[1][1] = 0;
    memset(vis, 0, sizeof(vis)); // 进去之后出来要刷新vis数组
    vis[1][1] = 1;
    dfs(1, 1, 0, -1);
    vis[1][1] = 0;
    memset(vis, 0, sizeof(vis)); // 进去之后出来要刷新vis数组
    cout << ans << endl;
}

算法2

(记忆化搜索+dp) // 时间复杂度应该是$O(n^2)$

参考博客：https://www.cnblogs.com/fancy-itlife/p/4298401.html

1. max_item加一是因为，防止出现最大价值为-1的情况，因为地面上的物品可能会存在0，所以最小的价值为-1
2. 需要写成longlong的形式，不然第三个样例就会错
3. 每个点有两种状态，拿东西或者不拿东西，但是要注意的是，我就算是手中最大的物品比这个点大也可以不拿

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define MOD % 1000000007
typedef long long ll;
using namespace std;

const int maxn = 56;
int n, m, k;
// dp[x][y][cnt][max_item+1] 的意思是
// 我从x，y这个点出发，手中有cnt件物品，物品最大的价值为max_item。走到终点有几种方案
ll dp[maxn][maxn][15][15];
ll mp[maxn][maxn];

int dfs(int x, int y, int cnt, int max_item)
{
    ll s = 0;
    // 如果这个点访问过，我就不继续走下去了
    if (dp[x][y][cnt][max_item + 1] != -1)
        return dp[x][y][cnt][max_item + 1];
    if (x == n && y == m) // 到达终点要返回
    {
        if (cnt == k) // 手中已经有了k件物品，那我就不拿了
        {
            return dp[x][y][cnt][max_item + 1] = 1;
        }
        else if (cnt == k - 1 && mp[x][y] > max_item) // 手中还可以再拿一件
        {
            return dp[x][y][cnt][max_item + 1] = 1;
        }
        else // 不足k件
        {
            return dp[x][y][cnt][max_item + 1] = 0;
        }
    }
    else
    {
        // 如果此时的物品大于我手中最大的价值，我有两种选择
        // 拿或者不拿
        if (mp[x][y] > max_item)
        {
            if (x + 1 <= n && x + 1 > 0) // 判断有没有出界
            {
                s = (s + dfs(x + 1, y, cnt + 1, mp[x][y]) MOD + dfs(x + 1, y, cnt, max_item) MOD) MOD;
            }
            if (y + 1 <= m && y + 1 > 0)
            {
                s = (s + dfs(x, y + 1, cnt + 1, mp[x][y]) MOD + dfs(x, y + 1, cnt, max_item) MOD) MOD;
            }
        }
        else //如果此时不大于，那就只能不拿
        {
            if (x + 1 <= n && x + 1 > 0)
            {
                s = (s + dfs(x + 1, y, cnt, max_item) MOD) MOD;
            }
            if (y + 1 <= m && y + 1 > 0)
            {
                s = (s + dfs(x, y + 1, cnt, max_item) MOD) MOD;
            }
        }
        return dp[x][y][cnt][max_item + 1] = s MOD;
    }
}

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