題目敘述
題目會給我們兩種無限量供應的骨牌Domino 和 Tromino，形狀分別如下
題目的輸入會有一個參數n。
可以任意旋轉方向進行拼接，請問最後拼成 2 x n 長方形區域的方法數有幾種?
例如 n = 3 時，拼成2 x 3 的長方形區域有五種方法。
測試範例
Example 1:
Input: n = 3
Output: 5
Explanation: The five different ways are show above.
Example 2:
Input: n = 1
Output: 1
約束條件
Constraints:
1 <= n <= 1000
參數n值介於1~1000之間。
演算法 DP + 觀察規律
這種計算方法數的題目，通常和兩類演算法有關
- 遞回。
為什麼? 因為主要是透過生成規律去推導遞迴關係式，進一步算出方法數。
- DP 動態規劃
為什麼? 因為如果純粹只依賴遞回計算，很可能會浪費很多時間在計算重複的子問題，因此需要透過DP動態規劃，去儲存已經計算過的答案，之後遇到重複的可以直接查表取得答案，提升演算法執行效率，減少時間複雜度。
