louisfghbvc的部落格

題目說明 :

在 2040 年，生物科技有了極大的發展，科學家們發現了基因的奧秘，基因科技創造出一個新品種的老鼠，每一年，一隻母鼠可以生一隻公鼠，而一隻公鼠會生一隻公鼠及母鼠，不過公鼠和母鼠在生完之後就會死去。因為創造過程中出了點小差錯，使得其中一隻母鼠永遠不會死，並且每年都會一樣生一隻公鼠。現在將這隻特別的母鼠放在一個空間中，請問 N 年後這個空間中會有幾隻公鼠還有幾隻母鼠。例如 N=3, 整個生育的樹狀圖如下圖。

菱形代表母鼠，圓形代表公鼠，黑色的圖代表死去的老鼠。

所以最後會有 4 隻公鼠、 3 隻母鼠。

輸入說明 :

輸入為一列資料，內容為一個正整數 N ，代表 N 年後。

輸出說明 :

輸出為一列資料，包含兩個大於等於零的整數分別代表 N 年後的公鼠及母鼠數量。

範例 :

思路:

觀察規律性, dp, 發現母的老鼠數量一定是前一年公的老鼠數量 + 1, 公的老鼠則是 前一年的所有老鼠數量

代碼:

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. int main()  
6. {  
7.     int n;  
8.     int dp[105][2];  
9.     dp[1][0] = dp[1][1] = 1;  
10.     while(cin >> n){  
11.         for(int i = 2; i <= n; ++i){  
12.             dp[i][0] = dp[i - 1][1] + 1;  
13.             dp[i][1] = dp[i - 1][1] + dp[i - 1][0];  
14.         }  
15.         cout << dp[n][1] << " " << dp[n][0] << endl;  
16.     }  
17.     return 0;  
18. }