Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
Problem:
https://www.geeksforgeeks.org/problems/ways-to-tile-a-floor5836/1
Ways To Tile A Floor
Difficulty: Medium Accuracy: 32.31%
Given a floor of dimensions 2 x n and tiles of dimensions 2 x 1, the task is to find the number of ways the floor can be tiled. A tile can either be placed horizontally i.e as a 1 x 2 tile or vertically i.e as 2 x 1 tile.
Note: Two tiling arrangements are considered different if the placement of at least one tile differs.
Examples :
Input: n = 3
Output: 3
Explanation: We need 3 tiles to tile the board of size 2 x 3.
We can tile in following ways:
1) Place all 3 tiles vertically.
2) Place first tile vertically and remaining 2 tiles horizontally.
3) Place first 2 tiles horizontally and remaining tiles vertically.
Input: n = 4
Output: 5
Explanation: We need 4 tiles to tile the board of size 2 x 4.
We can tile in following ways:
1) All 4 vertical
2) All 4 horizontal
3) First 2 vertical, remaining 2 horizontal.
4) First 2 horizontal, remaining 2 vertical.
5) Corner 2 vertical, middle 2 horizontal.
Constraints:
1 ≤ n ≤ 45
Solution:
class Solution:
def minSquares(self, n):
dp = [0] + [float('inf')] * n
for i in range(1, n + 1):
j = 1
while j * j <= i:
dp[i] = min(dp[i], 1 + dp[i - j * j])
j += 1
return dp[n]
Top comments (0)