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

Cut a Rectangle Into Squares

Find the fewest straight cuts needed to produce only squares.

Ce que vous allez apprendre

  • Define a DP table over width and height
  • Try every horizontal and vertical cut
  • Reuse results for smaller rectangles

Problème

Afficher la traduction

On each move, choose one rectangle and cut all the way across it, parallel to a side, making two rectangles with positive integer side lengths. Continue until every piece is a square. Squares may have different sizes. Count cuts, not pieces.

Implement rectangle_cutting(height, width).

Input

height: The starting rectangle height.

width: The starting rectangle width.

Output

Return the minimum number of cuts.

Contraintes

1 ≤ height, width ≤ 500. Rotation does not change the answer.

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

Cut off a 2 × 2 square, leaving a 2 × 1 rectangle. One more cut splits the remainder into two unit squares.

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

The starting rectangle is already a square.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

A rectangle can be solved by splitting it into two smaller rectangles and combining their best answers.

Indice 2

Try every possible horizontal and vertical cut to find the minimum.

Indice 3

Memoization or a table is helpful because many subrectangles repeat.

Complexité attendue

O(h*w*(h+w)) time, O(h*w) extra space

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.