蓝桥杯Python历届真题-地宫取宝（dfs深度优先搜索，保姆级注释，不懂来打我~）_宝石收集 2022蓝桥杯决赛

题目

题目要点

1. 这道题目有四个变量，分别为坐标x,y和手里拿到宝物的个数sum还有手里宝物的最大值max，一个一个来变换会比较乱+慢，故这里可以使用记忆性递归，四个变量一起捆绑往下走，不用每次都计算上一步的值。
2. “入口在左上角，出口在右上角”就可以知道递归的结束条件了。
3. “可以拿起它，当然也可以不拿”这一步就要看代码了，挺清晰的。
4. 还有一个要注意的点是，宝物的价值可能为0，故max（宝物的最大值）要设置-1为初始值，才有机会遍历到0。
5. 最后输出的t要进行取模，也就是：t%1000000007

dfs框架

1. 创建一个四维列表dp，同时储存4个变量x,y,sum,max（记忆性递归），只有dp被使用了才返回值(避免占用太多内存和时间)。
2. 考虑何时结束一次递归：
   到终点结束一次递归
   这个到终点只是从某起点出发到终点的一条路径，到终点后返回值
3. 过程：
   向下和向右递归：
   遍历所有从这个起点出发到终点的所有路径，并把过程中所有得到的t加起来，最后加起来之后的t也要返回值
   （而且过程中的每种情况都有可能是最后一步，所以每种情况后面都对t取模)

代码

n, m, k = map(int, input().split())
s=[]
for i in range(n):
    s.append(list(map(int, input().split())))
dp = [[[[-1]*15 for _ in range(15)]for _ in range(51)]for _ in range(51)]
#创建一个四维列表，每个值都为-1

def dfs(x, y, sum, max):
    #如果其中一个方案使用过了，不是-1了，就返回它的值（结合下面，即每个值都会返回一个t)
    if dp[x][y][sum][max+1] != -1: 
        return dp[x][y][sum][max+1] #因为题目中宝物价值包含0，所以max要从-1开始，从0开始的话，0处的宝物就不能被拾起了
    t = 0 #一开始的方案数
    
    #到达终点，也就是dfs的底
    if x==n-1 and y==m-1: #到达终点
        if s[x][y] > max: #比最大价值大
            if sum==k or sum==k-1: #手里的数量刚好为k或者差一个为k
                t+=1
        elif k==sum: #比最大价值小，但手里的数量刚好为k
            t+=1
        dp[x][y][sum][max+1]=t  
        return dp[x][y][sum][max+1] #返回某起点到了终点一趟的方案数
#为什么不直接return t是因为每次dfs完t变成0（看dfs前部分代码）只有return dp[x][y][sum][max+1]才能保留每次t的值并给到t

    if x+1 < n: #可以向下走
        #可选
        if s[x][y] > max: #比最大的大
            t += dfs(x+1, y, sum+1, s[x][y]) #这里的t就是，之前得到的t  +  从这里开始走到底（有可能有多种路径）得到的t, 下面类似的式子都同理
            t%=1000000007 #输出t对1000000007的取模结果
        #不选
        t += dfs(x+1, y, sum, max)  
        t%=1000000007

    if y+1<m:
        #可选
        if s[x][y]>max:
            t += dfs(x, y+1,sum+1,s[x][y]) 
            t%=1000000007
        #不选
        t += dfs(x, y+1, sum, max)
        t%=1000000007
        
    dp[x][y][sum][max+1] = t   #返回某起点到达终点所有路径得到的t    
    return dp[x][y][sum][max+1] 

print(dfs(0, 0, 0, -1)) #为了max能遍历到0，故要从-1开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46