【題目敘述】https://zerojudge.tw/ShowProblem?problemid=b229
【解題想法】觀察sample input，滾動DP
- 第一步可以往上、左、右走。
- 前一步往上走：這一步可以往上、左、右走。
- 前一步往左走：這一步可以往上、左走。
- 前一步往右走：這一步可以往上、右走。
#include <iostream>
using namespace std;
unsigned long long n, a, b, c, d;
int main() {
cin >> n;
a = 1;
b = 1;
for (int i = 1; i < n; i++){
c = a + b * 2;
d = a + b;
a = c;
b = d;
}
cout << a + b*2 << "\n";
}
#include <iostream>
using namespace std;
unsigned long long n;
unsigned long long dp[2][3];
int main() {
cin >> n;
dp[1][0] = 1; //up
dp[1][1] = 1; //left
dp[1][2] = 1; //right
int idx = 1;
for (int i=2; i<=n; i++){
idx = i % 2;
dp[idx][0] = dp[idx^1][0] + dp[idx^1][1] + dp[idx^1][2];
dp[idx][1] = dp[idx^1][0] + dp[idx^1][1];
dp[idx][2] = dp[idx^1][0] + dp[idx^1][2];
}
cout << dp[idx][0] + dp[idx][1] + dp[idx][2] << '\n';
}