Ways To Tile A Floor II
Dynamic Programming
easy
Score: 10
Given a floor of size n x m and tiles of size 1 x m. return the number of ways to tile the given floor using 1 x m tiles. A tile can either be placed horizontally or vertically. Both n and m are positive integers and 2 < = m.
Note: Return the total ways modulo 109 + 7.
Input Format:
First input- Number n.
Second input- Number m.
Output Format:
Return the number
Example 1:
Input: n = 2, m = 3
Output: 1
Explanation: There is only one way to tile the given floor.
Example 2:
Input: n = 4, m = 4
Output: 2
Explanation: There is two ways to tile the given floor. One way is to place 1 x 4 size of tile vertically and another one is to place them horizontally.
Constraints:
- 1 <= n <= 105
- 2 <= m <= 105
- Expected Time Complexity: O(n)
- Expected Space Complexity: O(n)