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.