Как покрыть квадратную комнату N × N наименьшим количеством квадратных плиток? (можно использовать повторно) ⇐ C++

[Anonymous]

Задача заключается в следующем:

Покройте квадратную комнату N × N квадратными плитками (не обязательно все плитки должны быть одинакового размера) без перекрытия, где длина стороны каждой плитки является целой и меньше N.
Каково минимальное количество плиток?


Мы вручную нарисовали несколько случаев низшего порядка, и текущее минимальное количество выглядит следующим образом:



N
текущее минимальное число/f(N)




3
6


4
4


5
8


6
4


7
9


8
4


9
6


10
4


11
11


13
13


17
12


k*n
f(n)|n простое



А вот код на основе dfs. Этот фрагмент кода надежен и способен выдать оптимальное решение, но он малоэффективен и поэтому предоставляется только для справки. Мы не проводили особых оптимизаций этого кода, так как считаем, что он не будет полностью соответствовать нашим требованиям, особенно когда N — большое простое число (например, 73).
Мы ищем ответы в виде эффективного кода (O[n^3] или ниже) или каких-либо ясных и строгих математических рассуждений, которые могут помочь продвинуться вперед.

Код: Выделить всё

#include 
using namespace std;
#define ll long long

const int inf=0x3f3f3f3f;

int vis[105][105];
int n;

bool judge(int i,int j,int k)
{
bool ans=true;
for(int ii=i;ii

Подробнее здесь: [url]https://stackoverflow.com/questions/79865714/how-to-cover-an-n-%c3%97-n-square-room-with-the-least-square-tiles-could-be-reused[/url]