Problema
Ad ogni mossa, scegli un rettangolo e taglialo completamente, parallelamente a un lato, ottenendo così due rettangoli con lati di lunghezza intera positiva. Continua finché ogni pezzo non è un quadrato. I quadrati possono avere dimensioni diverse. Conta i tagli, non i pezzi.
Implementa rectangle_cutting(height, width).
Input
height: L'altezza iniziale del rettangolo.
width: La larghezza iniziale del rettangolo.
Output
Restituisci il numero minimo di tagli.
Vincoli
1 ≤ height, width ≤ 500. Ruotare il rettangolo non cambia la risposta.
Esempi
Input:
width = 3
height = 2
Output atteso:
expected = 2Input:
long long width = 3;
long long height = 2;
Output atteso:
long long expected = 2;Input:
long width = 3;
long height = 2;
Output atteso:
long expected = 2;Spiegazione
Taglia un quadrato 2 × 2, lasciando un rettangolo 2 × 1. Un altro taglio divide il resto in due quadrati unitari.
Input:
width = 4
height = 4
Output atteso:
expected = 0Input:
long long width = 4;
long long height = 4;
Output atteso:
long long expected = 0;Input:
long width = 4;
long height = 4;
Output atteso:
long expected = 0;Spiegazione
Il rettangolo iniziale è già un quadrato.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Un rettangolo si può risolvere dividendolo in due rettangoli più piccoli e combinando le migliori risposte.
Suggerimento 2
Prova ogni possibile taglio orizzontale e verticale per trovare il minimo.
Suggerimento 3
La memoization o una tabella sono utili perché molti sottorettangoli si ripetono.
Complessità attesa
tempo O(h*w*(h+w)), spazio aggiuntivo O(h*w)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.