DP解思路:
直接求烷烃數目的複雜度有點高,所以可以先求的n碳的烷基數目。
求得烷基個數後,回來討論烷烃的情況,會有以下幾種:
(1)碳數為偶數:
1.可以分為兩個n/2個碳的烷基。
2.不能分為兩個n/2個碳的烷基。(提示:要找到一個3度碳或4度碳當作中心,讓連結的烷基碳數都小於n/2,在做計算)
(2)碳數為奇數:
1.可以分為一個(n+1)/2個碳的烷基,以及另一個(n-1)/2個碳的烷基。
2.不能分為一個(n+1)/2個碳的烷基,以及另一個(n-1)/2個碳的烷基。(提示同上)
另一可行解法:
這題其實可以用 波利亞計數原理(polya enumeration theorem) 來解,有興趣的人,就去Google或圖書館找找吧。(ps.因為我也還沒懂)