Domino and Tromino Tiling LeetCode solution in Rust

1
impl Solution {
2
  pub fn num_tilings(n: i32) -> i32 {
3
    // DP by considering filling the last column of space
4
    // T(n) = T(n - 1)      | end with one vertical domino
5
    //      + T(n - 2)      | end with two horizontal domino
6
    //      + T_up(n - 1)   | end with trimino filling the former lower grid
7
    //      + T_down(n - 1) | end with trimino filling the former upper grid//
8
    // T_up(n): having an unfilled lower grid, therefore it can be formed by
9
    // T_up(n) = T(n - 2)      | Fully filled followed with a trimino filling lower grid
10
    //         + T_down(n - 1) | T_down(n - 1) with an upper horizontal domino
11
    // T_down(n): equivalent as above
12
    // T_down(n) = T(n - 2)
13
    //           + T_up(n - 1)
14

15
    // To sum up:
16
    // T(n) = T(n-1) + T(n-2) + T_up(n-1) + T_down(n-1)
17
    // T_up(n-1) = T_down(n-2) + T(n-3)
18
    // T_down(n-1) = T_up(n-2) + T(n-3)
19
    // --> T(n) = T(n-1) + T(n-2) + T_down(n-2) + T(n-3) + T_up(n-2) + T(n-3)
20
    // --> T(n) = T(n-1) + T(n-3) + [T(n-2) + T(n-3) + T_up(n-2) + T_down(n-2)]
21
    // --> T(n) = 2 * T(n-1) + T(n-3)
22

23
    // Since every state change only concerns the previous three values
24
    // Space can be reduced to O(1) in three variables
25

26
    // Base case by reverse calculation:
27
    // Initially, T(0) = 0, T(1) = 1, T(2) = 2, T(3) = 5 ...
28
    // Thus, T(2) = 2 * T(1) + T(-1) --> T(-1) = 0
29
    //       T(1) = 2 * T(0) + T(-2) --> T(-2) = -1
30

31
    const MOD: i32 = 1_000_000_007;
32
    // T(n-3), T(n-2), T(n-1) respectively
33
    let (mut x, mut y, mut z) = (-1, 0, 1);
34
    for _ in 1..=n {
35
      let cur = (2 * z % MOD + x) % MOD; // mod everytime to prevent overflow
36
      x = y;
37
      y = z;
38
      z = cur;
39
    }
40
    z
41
  }
42
}