很好的递推题：铺磁砖和走格子

lpcpp

www.graptor.com
这是Matrix67.com的递推专项训练的题目，感觉很好。

*题一：用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板，共有多少种方案？
样例输入：2
样例输出：3

先设一个f表示i*3的地板铺的方法,f[1]=1;f[2]=3;
i*3的地板数是这样得到的：(i-1)*3的地板比i*3的地板少的地方全铺上1*1的瓷砖，这有一种铺法；
或者在(i-2)*3的地板比i*3的地板少的地方铺上2*2的瓷砖和2个1*1的瓷砖，这有两种铺法；
所以得到递推式：f=f[i-1]+2*f[i-2];

*题二：从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
样例输入：2
样例输出：7

这个我没想出来，看题解才弄明白。。
先设一个f表示恰好走i步且不经过已走的点 共有的走法。
如果向上走，不会出现经过已走的点；如果向左或右，上一步不能是向右或左。

引用题解上的一句话：/*
这一步的选择数= (3*上一步的所有选择中向上走的选择数) + (2*上一步的所有选择中向左、右走的选择数)。上一步的所有选择中向上走的选择数”实际上就是“上上步的所有选择数”即d[i-2]
*/引用结束

还有一点，就是“上一步的所有选择中向左、右走的选择数” 等于 “上步所有的选择数(即f[i-1])-上步向上的选择数”
也就等于 “上步所有的选择数(即f[i-1])-上上步所有的选择数(即f[i-2])”
所以得到递推式：f = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);

题解上共有五题，都很好，大家可以去这里看看：
http://www.fengzee.com/blog/article.asp?id=60

jking

ORZ，在这都能见到M67大牛的转载文