Handa_Rei level
获赞
47
粉丝
10
关注
0
看过 TA
714
华南理工大学
2024
C++
IP属地:广东
暂未填写个人简介
私信
关注
头像
2023-09-29 00:00
已编辑
华南理工大学 计算机类
利用记忆化搜索。python有装饰器cache可以用,遇到相同的参数会返回。防止了重复搜索。c++的话可以建立一个bool类型的四维数组,初始时全部为false。递归开头检查一下是否是true,是true就返回,否则就程序进行,并在结尾的时候把flag[x][y][z][i]设置为true,代表这种情况已经搜索过了。其实self.st完全没必要,只要设置一个cnt,满足的时候+=1。因为再次遇到相同的x,y,z,i,因为记忆化搜索所以会跳过。所以重复的数量不会加上。时间复杂度是o(abck)(因为每一种情况,至多会计算1次),因为abc的范围很小是1-100,所以是可以接受的。dfs的返回值没什么意义,不要思考,我敲出来后忘了删了。class Solution:    def howManyGoodComb(self, a: int, b: int, c: int, n: int):        self.st = set()        @cache        def dfs(x: int, y: int, z: int, i: int):            if x                 return 0            if i == 0:                tmp = sorted([x, y, z]) if tmp[0] + tmp[1] > tmp[2]:                    self.st.add((x, y, z))                    return 1                return 0            return dfs(x - i, y, z, i - 1) + dfs(x, y - i, z, i - 1) + dfs(x, y, z - i, i - 1)        ans = 0        for i in range(n + 1):            ans += dfs(a, b, c, i)        return self.st.__len__()
投递滴滴等公司10个岗位
0 点赞 评论 收藏
转发
牛客网
牛客企业服务