Tous les défis
Difficile 1 résolu 100.0 % de réussite

Découper un rectangle en carrés

Trouvez le nombre minimal de découpes droites nécessaires pour obtenir uniquement des carrés.

Ce que vous allez apprendre

  • Définir une table de DP sur la largeur et la hauteur
  • Essayer chaque coupe horizontale et verticale
  • Réutiliser les résultats des rectangles plus petits

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

Exemple 1
Entrée :
height = 2
width = 3

Sortie attendue :
expected = 2
Entrée :
long long height = 2;
long long width = 3;

Sortie attendue :
long long expected = 2;
Entrée :
long height = 2;
long width = 3;

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é.

Exemple 2
Entrée :
height = 4
width = 4

Sortie attendue :
expected = 0
Entrée :
long long height = 4;
long long width = 4;

Sortie attendue :
long long expected = 0;
Entrée :
long height = 4;
long width = 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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 954 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.