Tribonacci Sequence in Dynamic Programming

Enhancing DP skill

The problem

A man is trying to tile a wall. The wall has a height of 1 and a width of N. There are three types of tiles available:

1. A square tile with a height of 1 and a width of 1.
2. A rectangular tile with a height of 1 and a width of 2.
3. A rectangular tile with a height of 1 and a width of 3.

How many different ways are there to tile the wall? Note that tiles of the same type are not distinguished from each other. Additionally, tiles cannot be rotated or overlapped.

### Input
The input is given in the following format:

```
N
```

Where \( N \) is an integer satisfying the following constraint:
- \( N \) is an integer between 1 and 30 inclusive.

---

This problem requires determining the number of ways to tile a 1 by N wall using the given tile shapes.

The be-all and end-all is thinking about the last patterns we can take. In this case, we have three patterns such as using the tile with a width of 1, using the tile with a width of 2 and using the tile with a width of 3. Therefore, we can use this formula.

T(N)=T(N−1)​+T(N−2)​+T(N−3)​

My answer

func main() {
    var input int
    fmt.Scan(&input)
    if input < 0 {
        fmt.Println(0)
        return
    }

    accumulates := make([]int, input+1)
    
    if input >= 0 {
        accumulates[0] = 1
    }
    if input >= 1 {
        accumulates[1] = 1
    }
    if input >= 2 {
        accumulates[2] = 2
    }

    for i := 3; i <= input; i++ {
        accumulates[i] = accumulates[i-1] + accumulates[i-2] + accumulates[i-3]
    }

    fmt.Println(accumulates[input])
}

We can solve this problem with O(N).

Feel free to reach out to me on LinkedIn, which you can find below. Looking forward to connecting!

https://www.linkedin.com/in/tomoharu-tsutsumi-56051a126/