利用记忆化搜索。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__()