1196：踩方格

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

2

【输出样例】

7

解析：递推，对于当前步骤（i），前一步（i-1）东西走的，都有两种走法，向北走的有3种走法，上一步向北的走法数量刚好是大上一步（i-2）（因为大上一步每种走法都可以向北走一步），所以当前步骤的走法=上一步（i-1）*2+大上一步（i-2）详见代码：

#include <bits/stdc++.h>
using namespace std;
long long a[25];
int n;
int main() {
    cin >> n;
    a[1] = 3;
    a[2] = 7;
    for(int i = 3; i <= n; i++) {
        a[i] = a[i - 1] * 2 + a[i - 2];
    }
    cout << a[n];
    return 0;
}

 另一种递推：第一步向东西走的是2步（东西各一步），向北走的一步，第二步开始向北走的是上一步东西和北的和，向东西走的是上一步向北的2倍+向东西的一倍（原来向东的不能向西，向西的不能向东），详见代码：

#include <bits/stdc++.h>
using namespace std;
long long a[25];//向北步数
long long b[25];//向东西的步数
int n;
int main() {
    cin >> n;
    a[1] = 1;
    b[1] = 2;
    for(int i = 2; i <= n; i++) {
        a[i] = a[i - 1]  + b[i - 1];
        b[i] = 2 * a[i - 1] + b[i - 1];
    }
    cout << a[n] + b[n];
    return 0;
}