HDU 2563：無限平面上不回頭、不重複走格的 n 步方案數

問題背景

在一個無限大的二維平面上，我們從原點出發，每次只能移動一格（上、左、右），且不能向後走（即不能向下）。走過的格子會立即塌陷，無法再次踏足。給定步數 n (n ≤ 20)，求走 n 步的不同方案總數。兩種走法只要有一步不同，就視為不同方案。

輸入輸出格式

輸入第一行為測試組數 C，之後每行一個整數 n。對每組輸出走 n 步的方案數，每行一個結果。

遞推關係分析

定義兩類狀態：

• a[i]：第 i 步朝「前」（正方向）走的方案數；
• b[i]：第 i 步朝「左」或「右」走的方案數（因左右對稱，兩者相同）。

初始條件：a[1] = 3（可前、左、右），b[1] = 2（可左、右）。

對於 i > 1：

• 若第 i 步向前，則第 i-1 步可以是向前、向左或向右 → a[i] = a[i-1] + 2*b[i-1]；
• 若第 i 步向左（或右），則第 i-1 步只能是向前或向右（左）→ b[i] = a[i-1] + b[i-1]。

代碼實現

#include <stdio.h>

int main() {
    int a[21] = {0, 3}, b[21] = {0, 2}, i;
    for (i = 2; i < 21; i++) {
        b[i] = a[i-1] + b[i-1];
        a[i] = a[i-1] + 2 * b[i-1];
    }
    int m, N;
    scanf("%d", &N);
    while (N--) {
        scanf("%d", &m);
        printf("%d\n", a[m]);
    }
    return 0;
}

關鍵點總結

• 利用對稱性將狀態壓縮為兩個一維陣列；
• 預先計算 1..20 的所有答案，查詢時 O(1) 輸出；
• 結果在 32 位整數範圍內，無需大整數。