Question

pascal的问题

Answer 1

首先从题目的意思来看，c和c是可以排列在一起的
而本题可以使用动态规划的思想来解释
N个数的排列可以看成是N-1+1个数的排列
所以，要知道A【N】的值只需要知道A【N-1】中最后一位有多少是a或b（即后面可接除本身以外的两个数，记为M），又有多少是c（即后面可接abc三个数，记为N）。则A【N】=M*2+N*3；而用A【N-1】和A【N-2】便恰好可以得到M,N的数值。
从上面的式子可得到A【N-1】=M'*2+N'*3,而M'+N'=A【N-1】，所以N'=A【N-1】-2*A【N-2】即为A【N-2】中以c为最后一位的个数，接着得到M'=3*A【N-2】-A【N-1】；
进一步分析，当最后一位为c时，它的后面可以接a,b,c三种数字，而当它为a或者b的话，后面只能接两种数字——1个c，一个不是c。最后，我们就得到了M=M'+2*N'，N=M'+N'。
最后得到状态转移方程：

A【N】=2*A【N-1】+A【N-2】
这一题的难点便是动态规划的问题，如果你搞懂为什么‘只需要在N-1个固定排列的后面放如新数字，而不需要考虑插入的情况’这个问题，这一题也就只是一道很容易的数学分析题了。

纯手打，给个最佳呗！