So, I was looking through my notes to find what I've written in my spare time. Turns out, I have this problem written in one of the notes.↵
↵
I have an $N \times N$ square grid that needs to be fully covered with tiles. I can only use square tiles with the size of $i \times i$ where $1 \leq i \leq M$ to fill it. What is the minimum number of tiles needed to be used to fully cover the grid?↵
↵
For example: If $N = 9$ and $M = 5$, then the minimum number of tiles needed is $9$, since I can use nine $3 \times 3$ square tiles to fully cover the $9 \times 9$ grid.↵
↵
Constraint: $1 \leq M \leq N$↵
↵
Further Constraint: idk, since I don't know the fastest complexity for this.↵
↵
What is the fastest complexity and how to achieve it? Is it just brute force or is there an efficient algorithm to solve this?↵
↵
Edit: I just realised that this can be solved in around $O(N^2M)$ using simple DP. But can it be solved faster than that?↵
↵
Edit 2: Turns out, some value of $N$ and $M$ can't be solved with the simple DP. See [this](https://codeforces.net/blog/entry/117757?#comment-1041669).
↵
I have an $N \times N$ square grid that needs to be fully covered with tiles. I can only use square tiles with the size of $i \times i$ where $1 \leq i \leq M$ to fill it. What is the minimum number of tiles needed to be used to fully cover the grid?↵
↵
For example: If $N = 9$ and $M = 5$, then the minimum number of tiles needed is $9$, since I can use nine $3 \times 3$ square tiles to fully cover the $9 \times 9$ grid.↵
↵
Constraint: $1 \leq M \leq N$↵
↵
Further Constraint: idk, since I don't know the fastest complexity for this.↵
↵
What is the fastest complexity and how to achieve it? Is it just brute force or is there an efficient algorithm to solve this?↵
↵
Edit: I just realised that this can be solved in around $O(N^2M)$ using simple DP. But can it be solved faster than that?↵
↵
Edit 2: Turns out, some value of $N$ and $M$ can't be solved with the simple DP. See [this](https://codeforces.net/blog/entry/117757?#comment-1041669).
