还未发布过话题
  • 解题思路:
    1.设置矩阵高度和长度为 x,y;如 3,3 的矩阵如下,行代表次数,列代表环数
    [
    [0, 1, 2, 3],
    [0, 1, 2, 3],
    [0, 1, 2, 3]
    ]
    2.设 z 为目标总环数,f(x,y,z) 为可能的情况总数。
    推到出公式

    $$f(x,y,z)=\sum_{i=0}{n}f(x-1,y,z-i)$$

    def get_nums(length, height, nums):
        r = 0
        if length == 1:
            if 0 <= nums <= height:
                r = 1
            return r
        for i in range(height + 1):
            r += get_nums(length-1, height, nums-i)
        return r
    

    分析发现上面会进行很多无用的调用,导致执行时间太长,对调用过程进行剪裁,加入约束 z-y <= z-i <= (x-1)*y

    def get_nums(length, height, nums):
        r = 0
        if length == 1:
            if 0 <= nums <= height:
                r = 1
            return r
        for i in range(height + 1):
            if nums-height <= nums-i <= (length-1)*height:
                r += get_nums(length-1, height, nums-i)
        return r
    

    得出结果:92378