阿許某天在爬山的時候迷路了,
剛好身上帶著哨子,
就決定吹哨尋求援助!
但是吹哨時有分長音和短音,
而兩哨音之間要停頓別人才聽得清楚。
阿許吹哨的習慣是:
短音持續 1 秒,長音持續 2 秒,兩哨音中相隔 1 秒。
但由於迷路太緊張了,
忘記哨音到底要怎麼吹,
現在給你一個哨音的時間,( n 秒)
請你寫個程式幫阿許算出這個哨音有幾種吹法。
最後一個哨音要剛好在第 n 秒時結束。
每組測試資料有一個整數 n ( 0 < n ≤ 1000 )
每組測試資料輸出一行
在 n 秒內有幾種吹法
1 3 4 15
1 1 2 37
¤ Dynamic programming