HDU 2563 統計問題：遞推關係求走法數

問題

二維平面無限大，每步移動一格（上、左、右），不能後退（下），走過格子塌陷不可重複。求走 n（≤ 20）步的不同方案數。

狀態分析

設 x_n = 第 n 步向上的方案數，y_n = 向左/向右方案數，a_n = 總方案數。
遞推：
x_n = x_n-1 + y_n-1（向上只能從上一步任意方向來）。
y_n = 2x_n-1 + y_n-1（向左/右：從向上來有 2 選擇，從同方向來只能繼續同方向）。
a_n = x_n + y_n = 2a_n-1 + x_n-1 = 2a_n-1 + a_n-2。

遞推式

a[0] = 1, a[1] = 3。
a[n] = 2a[n−1] + a[n−2]。

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    vector a(21);
    a[0] = 1; a[1] = 3;
    for (int i = 2; i <= 20; ++i) a[i] = 2*a[i-1] + a[i-2];
    int T; cin >> T;
    while (T--) { int n; cin >> n; cout << a[n] << '\n'; }
    return 0;
}

複雜度

預處理 O(20)，查詢 O(1)。