一个智力题~

[hyh1048576]

先放难的版本：不超过 n 位，只包含 0、1、2，且 2 不在 1 后面的数有几个？

下面放一个容易一些的版本，想不出这个的可以看下面那道当提示。




















n 个杯子摆成一排，往里面投入硬币 0 - ⎡n/2⎤ 枚，要求每个杯子至多一枚，且任意两枚 coin 所在的杯子不相邻，有几种投法？

[Air_Mu]

出题要严谨 这样组织语言还是别出了。我说前面那个

[hyh1048576]

@Air_Mu 哪里不严谨了？

[hyh1048576]

@Air_Mu 我承认不够严谨。

这么说吧，由 A, B, C 组成且不含 AB 的长度为 n 的字符串有几个？

[zorksylar]

dp0[i] : 共i位，且含012，且2不在1后的方法数
dp1[i] : 共i位，且不含1的方法数
i >= 3
dp0[3] = 2
dp1[3] = 4

dp0[i] = dp0[i-1] * 2 + dp1[i-1]
dp1[i] = dp1[i-1] * 2

dp0[n] 为结果

[leixiao]

按最后一位的数字分类递推一下(包含了0可以在首位的情况):
发现其实是斐波那契数列
定义f(1)=1, f(2)=1, f(3)=2, f(4)=3, ... f(n)=f(n-1)+f(n-2)
那么不超过 n 位，只包含 0、1、2，且 2 不在 1 后面的数有f(2n+3)-2个

[dreambt]

@hyh1048576 2 不在 1 后面，是指2不能紧邻1后面，还是1必须在2左边出现（右边不可以）？
其次，简化问题并不等价于原问题：原题n位数，0肯定不能在最高位吧？而简化后的题目A可以在最左边

[Parallel]

@zorksylar DP正解。