“”is1(n)      再输出“”2+

　　问题描述

　　有一长度为 N(1<=Ｎ<=10)的地板，给定三种不同瓷砖：一种长度为 1，一种长度为 2，另一种长度为 3，数目不限。要将这个长度为 N 的地板铺满，

并且要求长度为 1 的瓷砖 不能相邻，一共有多少种不同的铺法？

　　例如，长度为 4 的地板一共有如下 4 种铺法：

　　4=1+2+1

　　4=1+3

　　4=2+2

　　4=3+1

　　编程求解上述问题。

　　第一种

输入格式

　　只有一个数 N，代表地板的长度。

　　输出格式

　　方案总数。

　　样例输入

　　4

　　样例输出

　　4

　　动态规划

　　n表示长度

　　最后一块不是1   (则是2或3)最后一块是1

　　总共               f_not1(1)=0

　　f_1(1)=1

　　f(1)f_not1(2)=1

　　f_1(2)=0

　　f(2)

　　f_not1(3)=2

　　f_1(3)=1

　　f(3)

　　f_not1(4)=f(1)+f(2)

　　铺满1块地板的数量（再铺一块3）+

　　铺满2块地板的数量（再铺一块2）

　　f_1(4)=f_not1(3)

　　最后一块不是1的f_not1(3)f(4)

　　f_not1(5)=f(2)+f(3)

　　铺满2块地板的数量（再铺一块3）+

　　铺满3块地板的数量（再铺一块2）

　　f_1(5)=f_not1(4)

　　最后一块不是1的f_not1(4)

　　f(5)

　　f_not1(6)=f(3)+f(4)

　　铺满3块地板的数量（再铺一块3）+

　　铺满4块地板的数量（再铺一块2）

　　f_1(6)=f_not1(5)                                f(6)………………

　　f_not1(n)=f(n-3)+f(n-2)

　　铺满n-3块地板的数量（再铺一块3）+

　　铺满n-2块地板的数量（再铺一块2）

　　f_1(n)=f_not1(n-1)f(n)

　　或者（只是看的方式不一样）

第一块不是1   (则是2或3)第一块是1

　　总共               f_not1(1)=0

　　f_1(1)=1

　　f(1)f_not1(2)=1

　　f_1(2)=0

　　f(2)

　　f_not1(3)=2

　　f_1(3)=1

　　f(3)

　　f_not1(4)=f(1)+f(2)

　　铺满最后1块地板的数量（第一块再铺一块3）+

　　铺满最后2块地板的数量（第一块再铺一块2）

　　f_1(4)=f_not1(3)

　　第一块不是1的f_not1(3)f(4)

　　f_not1(5)=f(2)+f(3)

　　铺满最后2块地板的数量（第一块再铺一块3）+

　　铺满最后3块地板的数量（第一块再铺一块2）

　　f_1(5)=f_not1(4)

　　第一块不是1的f_not1(4)

　　f(5)

　　f_not1(6)=f(3)+f(4)

　　铺满3块地板的数量（第一块再铺一块3）+

　　铺满4块地板的数量（第一块再铺一块2）

　　f_1(6)=f_not1(5)                                f(6)………………

　　f_not1(n)=f(n-3)+f(n-2)

　　铺满n-3块地板的数量（第一块再铺一块3）+

　　铺满n-2块地板的数量（第一块再铺一块2）

　　f_1(n)=f_not1(n-1)f(n)

　　参考代码

　　第一种

输入格式

　　只有一个数 N，代表地板的长度。

　　输出格式

　　每行一个方案，最后一行有一个数，代表方案总数。

　　样例输入

　　4

　　样例输出

　　4=1+2+1

　　4=1+3

　　4=2+2

　　4=3+1

　　4

第一块不是1第一块是1                   第一块是2第一块是3not1(1)=0is1(1)=1                          is2(1)=0

　　is3(1)=0

　　not1(2)=1

　　is1(2)=0=not1(1)

　　第一块不是1的1is2(2)=1

　　is3(2)=0

　　not1(3)=2=is2(3)+is3(3)

　　第一块不是3，

　　则是第一块是2和第一块是3的和

　　is1(3)=1=not1(2)

　　第一块不是1的2

　　is2(3)=1=f(1)

　　第一块是2，则还需铺满1is3(3)=1

　　not1(4)=f(1)+f(2)=is2(4)+is3(4)

　　is1(4)=not1(3)

　　第一块不是1的3

　　is2(4)=f(2)

　　第一块是2，则还需铺满2

　　is3(4)=f(1)

　　第一块是3，则还需铺满1

　　not1(5)=f(2)+f(3)=is2(4)+is3(5)

　　is1(5)=not1(4)

　　第一块不是1的4is2(4)=f(3)

　　第一块是2，则还需铺满3

　　is3(5)=f(2)

　　第一块是3，则还需铺满2

　　……………………not1(n)=f(n-3)+f(n-2)=is2(n)+is3(n)

　　is1(n)=not1(n-1)

　　is2(n)=f(n-2)

　　第一块是2，则还需铺满n-2

　　is3(n)=f(n-3)

　　第一块是3，则还需铺满n-3

　　输出时：先输出“”1+“”is1(n)      再输出“”2+“”is2(n)        最后输出   “”3+“”is1(3)

　　比如N=4

　　输出"1+"is1(4)

　　is1(4)就是not1(3)、not1(3)就是is2(3)和is3(3)、is2(3)就是2+1           is3(3)就是3                   所以输出1+2+1 和1+3