Problema
A cada movimento, escolha um retângulo e corte-o completamente, paralelo a um dos lados, formando dois retângulos com lados de comprimento inteiro positivo. Continue até que cada pedaço seja um quadrado. Os quadrados podem ter tamanhos diferentes. Conte os cortes, não os pedaços.
Implemente rectangle_cutting(height, width).
Entrada
height: A altura do retângulo inicial.
width: A largura do retângulo inicial.
Saída
Retorne o número mínimo de cortes.
Restrições
1 ≤ height, width ≤ 500. Rotacionar não altera a resposta.
Exemplos
Entrada:
width = 3
height = 2
Saída esperada:
expected = 2Entrada:
long long width = 3;
long long height = 2;
Saída esperada:
long long expected = 2;Entrada:
long width = 3;
long height = 2;
Saída esperada:
long expected = 2;Explicação
Corte um quadrado de 2 × 2, restando um retângulo de 2 × 1. Mais um corte divide o restante em dois quadrados unitários.
Entrada:
width = 4
height = 4
Saída esperada:
expected = 0Entrada:
long long width = 4;
long long height = 4;
Saída esperada:
long long expected = 0;Entrada:
long width = 4;
long height = 4;
Saída esperada:
long expected = 0;Explicação
O retângulo inicial já é um quadrado.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Um retângulo pode ser resolvido dividindo-o em dois retângulos menores e combinando as melhores respostas.
Dica 2
Teste todas as divisões horizontais e verticais para encontrar o mínimo.
Dica 3
Memoização ou uma tabela ajuda porque muitos subretângulos se repetem.
Complexidade esperada
tempo O(h*w*(h+w)), espaço extra O(h*w)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.