Tree就是一个游戏,你也可以玩
假设我们有无限量的灯球,用来装饰圣诞树
但是我们装饰是有规则的
1。任意灯球之间的电线不能闭环,不然就会短路。如下图中2,3两种情况都不能发生。
2。为了方便游戏,灯球的位置不同,以及电线的角度轨迹不同都依然算成相同的圣诞树。即4和5是完全一样的圣诞树。
3。为保证创新,每一颗圣诞树都不能包含之前的任何圣诞树。若6是一颗圣诞树,则7和8都包含了6,所以不算新的圣诞树。(单独解释8:在8中,蓝灯球和黄灯球最近的、共连的,是最底下的红灯球,这与6一致,所以也算重复)
4。为方便排序,第n颗圣诞树最多只能有n个灯球。
5。补充一下,每个灯球必须连上电线才能发光,除了第一个灯球,因为第一个灯球不论什么颜色本身就是电源,自己就会发光。如下图
Tree(n)就是当你有n种颜色的灯球时, 最多 能装饰多少颗不同的圣诞树
比如Tree(1)=1:只有一种颜色的灯球时,我 最多 只能装饰一颗圣诞树
Tree(2)=3:只有两种颜色的灯球时,我 最多 只能装饰3颗圣诞树
那么请聪明的小伙伴们算出Tree(3)等于多少吧!