再看分析

原题链接：5472.彼岸
userId_undefined

费先生

倔强青铜

2023-09-06 16:42:16

发布于：江苏

19阅读
0回复
0点赞

【分析】
f(n): n个单位空间的方案数 ；
f(1) = 3 ; 只有1个单位空间时，3种颜色珠子都满足要求；
f(2) = 9 ; 只有2个单位空间时，任选2种颜色的柱子都可以满足要求；
......
f(n) = f(n-1)*2 - f(n-2);
情况1： 最后3个珠子中只有2个相同，
当第n-2个珠子和第n-1个珠子相同时，第n个珠子只能和前2个不一样，有2种选择；
当第n-2个珠子和第n-1个珠子不相同时，第n个珠子只能和第n-1个珠子或者第n-2个珠子相同，也有2种选择；
综合一下，共有f(n-1)*2种方案 ；
情况2： 最后3个珠子都相同，那么第n个必须和第n-1个珠子一样，第n-1个珠子必须和第n-2个珠子一样，则有f(n-2)种方案 ；

userId_undefined
去预览
0/2000

全部评论 2

热门讨论