查找不同大小的多个返回语句的重复周期

Question

我有点纠结于如何为我的代码段创建递归，因为我们将有两次或三次调用函数的返回语句，这取决于堆栈是否有蓝色板。任何解决方案都将不胜感激！

该问题的Python代码如下所示：

def stack_plates(n, color, has_blue_plate):
if n == 0: 
return 1
if has_blue_plate:
return stack_plates(n-1, 'Blue', True) + 
stack_plates(n-1, 'Green', False)
else:
return stack_plates(n-1, 'Red', False) + 
stack_plates(n-1, 'Blue', True) + 
stack_plates(n-1, 'Green', False)

Answer 1

让我们将堆栈表示为一个数组(从左到右，而不是从下到上(。我们还将使用"；分离器"；(|(以便于表示。此外，让递归函数为count(n, c)，其中c表示要使用的颜色数。

考虑一堆n板。使用|标记堆叠中的第一个蓝色板，排列可能看起来像以下任意一个：

[ | (n-1)-length combination of B,G ]
[ (1)-length combination of R,G | (n-2)-length combination of B,G ]
[ (2)-length combination of R,G | (n-3)-length combination of B,G ]
...
[ (n-1)-length combination of R,G | ]
[ (n)-length combination of R,G ]

这里需要注意的几点：

1. 上面突出显示的事例不会相交，因为分隔符会为每个事例向右移动一个位置
2. 如果注意到模式，对于有效的x,y，即x+y = n-1，其中x和y分别是分隔符左侧和右侧的元素数，则排列数将为count(x,2) * count(y,2)
3. 综合所有安排，我们得到(count(0,2) * count(n-1,2)) + (count(1,2) * count(n-2,2)) + ... + (count(n-1,2) * count(0,2)) + (count(n,2))

把所有东西放在一起，我们得到以下递归：

count(n,3) = count(n, 2) + summation of (count(x,2) * count(n-1-x,2)) for all x between [0, n-1]

注：您可以将3和2分别替换为c和c-1，以获得具有c颜色的解决方案。