问题分析：
对于很多递归问题，我们都可以通过归纳总结来找出他们的规律：
当n=1时，way=1(横或竖)
当n=2时，way=2(全横或全竖)
当n=3时，way=3(全竖&横横竖&竖横横)
当n=4时，way=5(全竖&全横&竖横横竖&竖竖横横&横横竖竖)
当n=5时，way=8(全竖&竖横横竖竖&竖横横横横&竖竖横横竖&竖竖竖横横&横横竖竖竖&横横横横竖&横横竖横横)
.......
n=(n-1)+(n-2);
于是问题有转换成了之前的斐波那契数列问题了，依旧时同样的方法求解：
图片说明