寻找不同大小的多个返回语句的递归

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 ]

这里有几件事要注意：

上面突出显示的大小写不相交，因为分隔符对每种情况都右移一个位置。如果您注意到模式，对于有效的count(x,2) * count(y,2).

• Summing，对于有效的x,y，例如x+y = n-1，其中x和y分别是分隔符左边和右边的元素数，排列的数量将是(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(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颜色的解决方案。