首页 > 分享 > 画中漂流【第十一届第三场】【省赛】【B组】Python 【dfs =》记忆化搜索优化（建议学会用记忆化搜索）+dp（注意初始值的界定）】

画中漂流【第十一届第三场】【省赛】【B组】Python 【dfs =》记忆化搜索优化（建议学会用记忆化搜索）+dp（注意初始值的界定）】

花匠小妙招
2024-12-07 19:41

题目
在这里插入图片描述
分析
求方案总数，容易想到dfs搜索，搜索携带三个参数T M D 代表

距离救援还有 T 分钟，还剩 M 点体力，距离峡谷还有 D 米

dfs 搜，但是超时！

MOD=int(1e9+7) cnt=0 def dfs(T,M,D):#距离救援还有 T 分钟，还剩 M 点体力，距离峡谷还有 D 米 global cnt if T==0:#救援到达 if M==0:#体力需要在救援前花光 cnt = (cnt+1)%MOD return if M>0: dfs(T-1,M-1,D+1)#消耗体力，远离峡谷 if D>1: dfs(T-1,M,D-1)#不消耗体力，靠近峡谷 D,T,M = map(int,input().split()) dfs(T,M,D) print(cnt)

1234567891011121314151617

看数据范围，很容易超时
在这里插入图片描述

f[T][M]表示救援时间T，体力M时划的方案数
注意f 默认为-1

记忆化搜索

MOD=int(1e9+7) f=[[-1]*(1510) for i in range(3010)] #f[T][M]表示T分种M点体力的方案数,记忆化搜索默认-1 def dfs(T,M,D):#距离救援还有 T 分钟，还剩 M 点体力，距离峡谷还有 D 米 if f[T][M]!=-1: return f[T][M] if T==0:#救援到达 if M!=0: return 0 #如果救援达到体力没花光，返回0 return 1 #如果体力花光，算1次方案 f[T][M]=0 if M>0: f[T][M]=(f[T][M]+dfs(T-1,M-1,D+1))%MOD if D>1: f[T][M]=(f[T][M]+dfs(T-1,M,D-1))%MOD return f[T][M] D,T,M = map(int,input().split()) print(dfs(T,M,D))

123456789101112131415161718192021

dp，参考别人思路界定初始值（没看懂）

MOD=int(1e9+7) D,T,M = map(int,input().split()) dp=[[0]*(1510) for i in range(3010)] #dp[i][j]表示i秒j点体力的方案数量 for i in range(1,T+1): for j in range(1,M+1):#j>i时候，救援时间到了体力没消耗完，肯定为0 if j*2<i:#2倍体力<救援时间,一直向前游也会掉下去， dp[i][j]=0 elif i==j:#当i=j时因为要把体力用完只能选择一直向前游,一种解法。 dp[i][j]=1 elif i-1==j:#当i-1=j 第一秒只能选择向前游，不游的那一秒还剩i-1种选择空间，所以有i-1种解法 dp[i][j]=i-1 else: dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD print(dp[T][M])

1234567891011121314151617