4.19 阿里笔试 捞鱼用dfs超时，dp又写不出QAQ
这道题目用DFS感觉非常直观，但是复杂度是10^200，肯定超时的嘛😂
def getMaximunFishByDfs(self, n, w, b, x, a, cost): def dfs(count, energy, energy_bound, idx): if idx == n: if count > self.res: self.res = count return get_fish = 0 while energy - cost[idx] >= 0 and get_fish <= a[idx]: #体力要足够 if get_fish > 0: # 不捞鱼的情况特殊处理 energy -= cost[idx] energy_bound += b if energy + x > energy_bound: dfs(count + get_fish, energy_bound, energy_bound, idx + 1) else: dfs(count + get_fish, energy + x, energy_bound, idx + 1) get_fish += 1 self.res = 0 dfs(0, w, w, 0) return self.res
如果用DP[i][j]代表代表体力为 j 的人去捞前 i 个鱼塘最多能捕到多少条鱼，由于体力上限的存在会导致情况非常复杂，而且空间复杂度到达了10^11，肯定超空间😓
我的小脑袋瓜想破头了也想不出，有人有思路吗，能贴伪代码就更好了🤣
#笔试题目##阿里巴巴#
腾讯一面1066人在聊