1436: 蓝桥杯2014年第五届真题-地宫取宝（Python3）

解题思路:
参考：https://blog.csdn.net/u014665013/article/details/45201479

注意事项:
DFS+记忆化搜索

参考代码:

def dfs(x, y, loads: int, max_value: int):
    global map_, n, m, k, dp

    if dp[x][y][loads][max_value + 1] != -1:  # visited
        return dp[x][y][loads][max_value + 1]
    if x == n - 1 and y == m - 1:  # destination
        if loads == k or (loads == k - 1 and map_[x][y] > max_value):
            dp[x][y][loads][max_value + 1] = 1
            return 1
        else:
            dp[x][y][loads][max_value + 1] = 0
            return 0
    a = 0
    current_value = map_[x][y]
    for directions in [[0, 1], [1, 0]]:  # right, down
        if x + directions[0] < n and y + directions[1] < m:  # index check
            if current_value > max_value and loads < k:  # value check
                a += dfs(x + directions[0], y + directions[1], loads + 1, current_value)  # take
            a += dfs(x + directions[0], y + directions[1], loads, max_value)
    dp[x][y][loads][max_value + 1] = a
    return dp[x][y][loads][max_value + 1]

n, m, k = map(int, input().split())
map_ = [list(map(int, input().split())) for _ in range(n)]
dp = [[[[-1 for _ in range(14)] for _ in range(13)] for _ in range(m + 1)] for _ in range(n + 1)]
print(dfs(0, 0, 0, -1) % 1000000007)