動態規劃-排列組合

題目1552：座位問題
時間限製：1 秒內存限製：128 兆特殊判題：否提交：313

解決：95
題目描述：
計算機學院的男生和女生共n個人要坐成一排玩遊戲，因為計算機的女生都非常害羞，男生又很主動，所以活動的組織者要求在任何時候，一個女生的左邊或者右邊至少有一個女生，即每個女生均不會隻與男生相鄰。現在活動的組織者想知道，共有多少種可選的座位方案。例如當n為4時，共有
女女女女, 女女女男, 男女女女, 女女男男, 男女女男, 男男女女, 男男男男 7種。
輸入：
輸入包含多組測試用例，每組測試用例僅包含一個整數n(1<=n<=1000)。
輸出：
對於每組測試用例，輸出一個數代表可選的方案數，為防止答案過大，答案對1000000007取模。
樣例輸入：
1
2
4
樣例輸出：
1
2
7
來源：
2014年王道論壇研究生機試練習賽（三）

最後更新：2017-04-03 12:55:38