解题思路:
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