難度: Medium
類型: Dynamic Programming
CPP程式下載: 790.cpp
前情題要:
2*1 的骨牌, 與2*2缺一格的骨牌組合(可旋轉)。有多少種組合方式能得到一個2*n的長條形。(數字很大, 必須 modulo 10^9+7)
思考方式:
老實說, 這一題對我來說很難。而且我認為這題是數學題, 而不是 Dynamic Programming。如果想得到很棒的數學表示方式, 那就能用很精簡的程式算出答案。
1. 定義 F(N) 和 G(N)。F(N) 是組成2*N的長條形的可能組合個數。G(N)是組成2*N長條形卻缺了右下一格的組合個數。
2. F(N)=2*G(N-1)+F(N-2)+F(N-1) :
(2-1) G(N-1), 右下缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。
(2-2) G(N-1), 右上缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。
(2-3) F(N-2), 配上兩個橫置並排 2*1 的骨牌, 能構成 F(N)
(2-4) F(N-1), 配上一個 2*1 的骨牌, 能構成 F(N)
3. G(N)=G(N-1)+F(N-2) :
(3-1) G(N-1) 缺右下的改成缺右上的, 個數一樣, 再搭配一個2*1的骨牌橫置擺在右上那一排, 就成了G(N)缺右下的。
(3-2) F(N-2) 就是 2*(N-2) 的長條形配上一個2*2但右下缺一格的骨牌, 就成了G(N)。
複雜度思考:
Time Complexity: O( 2*N )
Space Complexity: O( x )
結果:
Runtime: 0 ms, Beats: 100%
Memory: 8.33 MB, Beats: 8.94%
