Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Cut a Rectangle Into Squares

Find the fewest straight cuts needed to produce only squares.

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
height = 2
width = 3

Erwartete Ausgabe:
expected = 2
Eingabe:
long long height = 2;
long long width = 3;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long height = 2;
long width = 3;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

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

Beispiel 2
Eingabe:
height = 4
width = 4

Erwartete Ausgabe:
expected = 0
Eingabe:
long long height = 4;
long long width = 4;

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long height = 4;
long width = 4;

Erwartete Ausgabe:
long expected = 0;

Erläuterung

The starting rectangle is already a square.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

Memoization or a table is helpful because many subrectangles repeat.

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 954 ms - 4/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.