Problema
En cada movimiento, elige un rectángulo y córtalo completamente, en línea recta y paralelo a uno de sus lados, dividiéndolo en dos rectángulos con lados de longitud entera positiva. Continúa hasta que cada pieza sea un cuadrado. Los cuadrados pueden ser de diferentes tamaños. Cuenta los cortes, no las piezas.
Implementa rectangle_cutting(height, width).
Entrada
height: La altura inicial del rectángulo.
width: El ancho inicial del rectángulo.
Salida
Devuelve el número mínimo de cortes.
Restricciones
1 ≤ height, width ≤ 500. Rotar el rectángulo no cambia la respuesta.
Ejemplos
Entrada:
width = 3
height = 2
Salida esperada:
expected = 2Entrada:
long long width = 3;
long long height = 2;
Salida esperada:
long long expected = 2;Entrada:
long width = 3;
long height = 2;
Salida esperada:
long expected = 2;Explicación
Corta un cuadrado de 2 × 2, dejando un rectángulo de 2 × 1. Un corte más divide el resto en dos cuadrados de 1 unidad.
Entrada:
width = 4
height = 4
Salida esperada:
expected = 0Entrada:
long long width = 4;
long long height = 4;
Salida esperada:
long long expected = 0;Entrada:
long width = 4;
long height = 4;
Salida esperada:
long expected = 0;Explicación
El rectángulo inicial ya es un cuadrado.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Un rectángulo se puede resolver dividiéndolo en dos rectángulos más pequeños y combinando sus mejores respuestas.
Pista 2
Prueba cada corte horizontal y vertical posible para encontrar el mínimo.
Pista 3
La memoización o una tabla ayudan porque muchos subrectángulos se repiten.
Complejidad esperada
tiempo O(h*w*(h+w)), espacio extra O(h*w)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.