這是Matrix67.com的遞推專項訓(xùn)練的題目，感覺很好。
*題一：用1 x 1和2 x 2的磁磚不重疊地鋪滿N x 3的地板，共有多少種方案？
樣例輸入：2
樣例輸出：3
先設(shè)一個f[i]表示i*3的地板鋪的方法,f[1]=1;f[2]=3;
i*3的地板數(shù)是這樣得到的：(i-1)*3的地板比i*3的地板少的地方全鋪上1*1的瓷磚，這有一種鋪法；
或者在(i-2)*3的地板比i*3的地板少的地方鋪上2*2的瓷磚和2個1*1的瓷磚，這有兩種鋪法；
所以得到遞推式：f[i]=f[i-1]+2*f[i-2];
*題二：從原點出發(fā)，一步只能向右走、向上走或向左走。恰好走N步且不經(jīng)過已走的點共有多少種走法？
樣例輸入：2
樣例輸出：7
這個我沒想出來，看題解才弄明白。。
先設(shè)一個f[i]表示恰好走i步且不經(jīng)過已走的點 共有的走法。
如果向上走，不會出現(xiàn)經(jīng)過已走的點；如果向左或右，上一步不能是向右或左。
引用題解上的一句話：/*
這一步的選擇數(shù)= (3*上一步的所有選擇中向上走的選擇數(shù)) + (2*上一步的所有選擇中向左、右走的選擇數(shù))。上一步的所有選擇中向上走的選擇數(shù)”實際上就是“上上步的所有選擇數(shù)”即d[i-2]
*/引用結(jié)束
還有一點，就是“上一步的所有選擇中向左、右走的選擇數(shù)” 等于 “上步所有的選擇數(shù)(即f[i-1])-上步向上的選擇數(shù)”
也就等于 “上步所有的選擇數(shù)(即f[i-1])-上上步所有的選擇數(shù)(即f[i-2])”
所以得到遞推式：f[i] = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);
題解上共有五題，都很好，大家可以去這里看看：
http://www.fengzee.com/blog/article.asp?id=60