// No.44 DPなすごろく // https://yukicoder.me/problems/no/44 // #include #include #include #include using namespace std; long long int solve(unsigned int N); int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); unsigned int N; cin >> N; long long ans = solve(N); cout << ans << endl; } long long int solve(unsigned int N) { vector> dp; dp.resize(N+1); for (auto y = 0; y< N+1; ++y) dp[y].resize(N+1); dp[0][0] = 1; for (auto i = 1; i <= N; ++i) { for (auto j = i; j <= N; ++j) { long long t = 0; for (auto k = 1; k <= 2; ++k) { if (j - k < 0) continue; t += dp[i-1][j-k]; } dp[i][j] = t; } } long long total = 0; for (auto i = 0; i <= N; ++i) total += dp[i][N]; return total; }