Tutte le sfide
Difficile 1 risolta 100.0% di accettazione

Taglia un Rettangolo in Quadrati

Trova il minor numero di tagli rettilinei necessari per ottenere solo quadrati.

Cosa imparerai

  • Definire una tabella DP su larghezza e altezza
  • Provare ogni taglio orizzontale e verticale
  • Riutilizzare i risultati dei rettangoli più piccoli

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

Esempio 1
Input:
height = 2
width = 3

Output atteso:
expected = 2
Input:
long long height = 2;
long long width = 3;

Output atteso:
long long expected = 2;
Input:
long height = 2;
long width = 3;

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.

Esempio 2
Input:
height = 4
width = 4

Output atteso:
expected = 0
Input:
long long height = 4;
long long width = 4;

Output atteso:
long long expected = 0;
Input:
long height = 4;
long width = 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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 ННикита Python 954 ms - 4/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 1 soluzione completa sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.