动态规划加深序遍历（代码注释）

解题思路:

注意事项:

参考代码:

n,m,k=map(int,input().split())
# 记录迷宫的宝贝价值
table=[]
for _ in range(n):
    table.append(list(map(int,input().split())))
# 状态列表dp[1][2][3][4]=5 表示坐标（1,2)这个点物品数量为3最大价值为4的方案有5种
dp=[[[[-1]*15 for _ in range(15)] for _ in range(51)]for _ in range(51)]
#深度遍历
def dfs(x,y,sum,max):
    #因为如果这个方案先前采用了，就会有一个值而不是初始值-1
    if dp[x][y][sum][max+1]!=-1:
        #直接将记录过的状态返回
        return dp[x][y][sum][max+1]
    #方案数
    t=0
    #到达终点
    if x==n-1 and y==m-1:
        #最后一个格子能选
        if table[x][y]>max:
            #可选可不选，若选那么只能再选最后一个（先前有k-1个)
            if sum==k or sum==k-1:
                t+=1
        elif k==sum:
            #不能选也算一种方案
            t+=1
        dp[x][y][sum][max+1]=t
        #返回终点的方案数
        return dp[x][y][sum][max+1]
    #向下走
    if x+1<n:
        #可选
        if table[x][y]>max:
            t+=dfs(x+1,y,sum+1,table[x][y])
            t%=1000000007
        #不选
        t+=dfs(x+1,y,sum,max)
        t%=1000000007
        #向右走
    if y+1<m:
        #可选
        if table[x][y]>max:
            t+=dfs(x,y+1,sum+1,table[x][y])
            t%=1000000007
        #不选
        t+=dfs(x,y+1,sum,max)
        t%=1000000007
    dp[x][y][sum][max+1]=t
    return dp[x][y][sum][max+1]
dp[0][0][0][0]=dfs(0,0,0,-1)
print(dp[0][0][0][0])