首页 > 4.19 阿里笔试 捞鱼用dfs超时,dp又写不出QAQ
头像
丁丁冒险记
编辑于 2021-05-04 16:16
+ 关注

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,肯定超空间😓
我的小脑袋瓜想破头了也想不出,有人有思路吗,能贴伪代码就更好了🤣

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐