leetcode-790 多米诺和托米诺平铺

题目

题目链接

分析

• 题目要求 1x2 和 ‘L’型 的多米诺骨牌和 2x2 的托米诺骨牌，覆盖一个 2xn 的平面
• 初步判断dp 因为后续状态可以由前面状态推导出来
• 极速版：
  • dp[i] = dp[i-3] + dp[i-1] * 2 i > 3,(n>0)
  • 初始态 dp[1] = 1, dp[2] = 2, dp[3] = 5
• 推演版：
  • 四个状态
    • dp[i][0] = dp[i-1][3]（当前列空）
    • dp[i][1] = dp[i-1][0] + dp[i-1][2]（当前列下方空）
    • dp[i][2] = dp[i-1][0] + dp[i-1][1]（当前列上方空）
    • dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]（当前列满）
  • 初始版
    • dp[i][0] = 0
    • dp[i][1] = 0
    • dp[i][2] = 0
    • dp[i][3] = 1

源代码

源代码