考慮在 X-Y 平面上的整數格子點上建構長度為 N 的路徑。其中在格子點 (x, y) 時，路徑可以往右走到格子點 (x+1, y)；或往左走到格子點 (x-1, y)；或往上走到格子點 (x, y+1)。長度為 N 的路徑必須經過 N 個相異的邊。試問由原點 (0, 0) 出發並按照上述規則所形成長度為 N 的路徑有幾條？
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| EOF 輸入，輸入僅有一列，包含一個正整數 N (1 <= N <= 50)。 | 輸出所有由原點 (0, 0) 出發且長度為 N 的路徑總數。 |
| 1 3 | 3 17 |
解題思路
計算本題答案時需要使用 unsigned long long int。宣告一個陣列 ans 用來建表，並且將其的前 4 個位置之資料設為 0、3、7、17。之後跑一個 For迴圈 從 4 到 50，並且將 ans[目前位置] 設為 ans[目前位置-1] * 2 + ans[目前位置-2]。
範例程式碼－ZeroJudge B229: 路徑問題
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
unsigned long long int N, ans[100] = {};
ans[0] = 0;
ans[1] = 3;
ans[2] = 7;
ans[3] = 17;
for (int i = 4; i<=50; i++) {
ans[i] = ans[i-1] * 2 + ans[i-2];
}
while (cin >> N) {
cout << ans[N] << "\n";
}
}
//ZeroJudge B229
//Dr. SeanXD