Problème
À chaque étape, choisissez un rectangle et coupez-le entièrement, parallèlement à l'un de ses côtés, de façon à obtenir deux rectangles dont les côtés sont des entiers strictement positifs. Continuez jusqu'à ce que chaque morceau soit un carré. Les carrés peuvent être de tailles différentes. Comptez le nombre de découpes, pas le nombre de morceaux.
Implémentez rectangle_cutting(height, width).
Entrée
height : La hauteur du rectangle de départ.
width : La largeur du rectangle de départ.
Sortie
Retournez le nombre minimal de découpes.
Contraintes
1 ≤ height, width ≤ 500. La rotation ne change pas la réponse.
Exemples
Entrée :
width = 3
height = 2
Sortie attendue :
expected = 2Entrée :
long long width = 3;
long long height = 2;
Sortie attendue :
long long expected = 2;Entrée :
long width = 3;
long height = 2;
Sortie attendue :
long expected = 2;Explication
Découpez un carré de 2 × 2, il reste un rectangle de 2 × 1. Une découpe supplémentaire sépare le reste en deux carrés unité.
Entrée :
width = 4
height = 4
Sortie attendue :
expected = 0Entrée :
long long width = 4;
long long height = 4;
Sortie attendue :
long long expected = 0;Entrée :
long width = 4;
long height = 4;
Sortie attendue :
long expected = 0;Explication
Le rectangle de départ est déjà un carré.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Un rectangle peut être résolu en le divisant en deux plus petits rectangles et en combinant leurs meilleures réponses.
Indice 2
Teste toutes les coupures horizontales et verticales possibles pour գտiver le minimum.
Indice 3
La mémoïsation ou un tableau aide beaucoup, car de nombreux sous-rectangles se répètent.
Complexité attendue
temps O(h*w*(h+w)), espace supplémentaire O(h*w)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.