9.28 滴滴第一题

利用记忆化搜索。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 <= 0 or y <= 0 or z <= 0:
                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__()