付費限定文章

一魚多吃 用DP解 骨牌拼接 Domino and Tromino Tiling_Leetcode 790 精選75題

Filipp Romanovski on Unsplash

題目敘述

題目會給我們兩種無限量供應的骨牌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 + 觀察規律

這種計算方法數的題目，通常和兩類演算法有關

1. 遞回。

為什麼? 因為主要是透過生成規律去推導遞迴關係式，進一步算出方法數。

2. DP 動態規劃