Problem Description 在一无限大的二维平面中，我们做如下假设： 1、 每次只能移动一格； 2、 不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）； 3、 走过的格子立即塌陷无法再走第二次； 求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。 Input 首先给出一个正整数C，表示有C组测试数据 接下来的C行，每行包含一个整数n (n<=20)，表示要走n步。 Output 请编程输出走n步的不同方案总数； 每组的输出占一行。 Sample Input 2 1 2 Sample Output 3 7 Author yifenfei
思路：递推方法。
详见代码。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; ///f(i) = a[i] +b[i] 代表第i步的总步数是向上走的步数a[i]加上向左或向右的步数b[i]。 ///现在假设第i步向上走，那么第i - 1步可以向上走即a[i - 1],还可以向左或向右走即b[i - 1]。那么a[i] = a[i - 1] + b[i - 1] ///假设第i步向左或者向右走，那么第i - 1步先向上走，再向左或向右走，那么此时就有两种情况，且步数相同，也就是2*a[i -1] ///如果第i - 1步就是向右走，那么第i步也只能向右走，如果是向左走的，那么就只能向左走，所以只有一种情况，也就是b[i - 1] 此时的到f[i] = 2 * a[i - 1] + b[i - 2] ///由上面的可知道 f[n] = 2*f[n - 1] + f[n - 2] int main() { int C; scanf("%d",&C); int a[21]; a[1] = 3, a[2] = 7; for(int i = 3; i <= 20; i++) a[i] = 2 * a[i - 1] + a[i - 2]; while(C--) { int n; scanf("%d",&n); printf("%d\n",a[n]); } return 0; }
