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

题目

分析
求方案总数，容易想到dfs搜索，搜索携带三个参数T M D 代表

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

dfs 搜，但是超时！

MOD=int(1e9+7)
cnt=0
def dfs(T,M,D):#距离救援还有 T 分钟，还剩 M 点体力，距离峡谷还有 D 米global cntif T==0:#救援到达if M==0:#体力需要在救援前花光cnt = (cnt+1)%MODreturnif 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)

看数据范围，很容易超时

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 #如果救援达到 体力没花光，返回0return 1 #如果体力花光，算1次方案f[T][M]=0if M>0:f[T][M]=(f[T][M]+dfs(T-1,M-1,D+1))%MODif D>1:f[T][M]=(f[T][M]+dfs(T-1,M,D-1))%MODreturn f[T][M]D,T,M = map(int,input().split())
print(dfs(T,M,D))

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时候，救援时间到了体力没消耗完，肯定为0if j*2<i:#2倍体力<救援时间,一直向前游也会掉下去，dp[i][j]=0elif i==j:#当i=j时因为要把体力用完 只能选择一直向前游,一种解法。dp[i][j]=1elif i-1==j:#当i-1=j 第一秒只能选择向前游，不游的那一秒还剩i-1种选择空间，所以有i-1种解法dp[i][j]=i-1else:dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MODprint(dp[T][M])

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！