LeetCode 75 C++ | Step-by-Step Solutions (LAN Academy) - LeetCode 790: Domino and Tromino Tiling — DP Explained (O(1) Space)

Solve LeetCode 790 — Domino and Tromino Tiling using Dynamic Programming. We want the number of ways to tile a 2 × n board using: Domino (2×1) tiles (rotations allowed) Tromino (L-shape) tiles (rotations allowed) DP Idea A clean way is to use two states: full[i] = ways to fully tile a 2×i board gap[i] = ways to tile a 2×i board with one cell missing (a “staggered” board) Recurrences: full[i] = full[i−1] + full[i−2] + 2·gap[i−1] gap[i] = gap[i−1] + full[i−2] All answers are computed mod 1e9+7. (You can also derive the well-known single recurrence: full[i] = 2·full[i−1] + full[i−3], for i ≥ 3.) Complexity Time: O(n) Space: O(1) (rolling variables) If this helped, subscribe for more DP patterns and interview problems. #LeetCode #DynamicProgramming #Algorithms #codinginterview #leetcode #leetcodecoding #leetcodesolution #leetcodechallenge #faang #fang #computerscience #cs #codingtiktok #coding #codinglife #boostofhope #fyp #codinginterview #softwareengineer #swe #tech #foryou #python #learntocode #google #techtok #programming #algorithms #learntocode