No.44 DPなすごろく

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 300
作問者 : yuki2006yuki2006

3 ProblemId : 76

問題文

あなたは、Nマスのすごろくをしている。
毎ターン「1」または「2」前に進むことができる。
あなたは最初「0」のマスのスタートにいる。

ちょうどNマスに行く方法は何パターンありますか?


入力

N

すごろくのマス 整数\( N (2 \le N \le 50) \) が与えられます。

出力

ちょうどNマスにいく行く方法のパターン数を求めてください。
答えは\(2^{32} \) に収まらない時があるので注意です。

サンプル

サンプル1
入力
2
出力
2

2に行く方法は「1・1」と「2」の2パターンです。

サンプル2
入力
3
出力
3

3に行く方法は「1・1・1」と「2・1」と「1・2」の3パターンです。

「2・1」と「1・2」は区別するのでご注意ください。

サンプル3
入力
5
出力
8

「1・1・1・1・1」
「2・1・1・1」
「1・2・1・1」
「1・1・2・1」
「1・1・1・2」
「1・2・2」
「2・1・2」
「2・2・1」
の8通り

サンプル4
入力
50
出力
20365011074

答えは\(2^{32} \) を超えるのでintでは収まりません。

提出ページヘ