Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Schneide ein Rechteck in Quadrate

Finde die minimale Anzahl gerader Schnitte, um nur Quadrate zu erhalten.

Das lernst du

  • Eine DP-Tabelle über Breite und Höhe definieren
  • Jeden horizontalen und vertikalen Schnitt ausprobieren
  • Ergebnisse kleinerer Rechtecke wiederverwenden

Problem

Wähle bei jedem Zug ein Rechteck aus und schneide es vollständig, parallel zu einer Seite, sodass zwei Rechtecke mit positiven ganzzahligen Seitenlängen entstehen. Fahre fort, bis jedes Teilstück ein Quadrat ist. Die Quadrate dürfen unterschiedlich groß sein. Zähle die Schnitte, nicht die Stücke.

Implementiere rectangle_cutting(height, width).

Eingabe

height: Die Höhe des Startrechtecks.

width: Die Breite des Startrechtecks.

Ausgabe

Gib die minimale Anzahl der benötigten Schnitte zurück.

Einschränkungen

1 ≤ height, width ≤ 500. Eine Drehung verändert die Antwort nicht.

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

Schneide ein 2 × 2 Quadrat ab, es bleibt ein 2 × 1 Rechteck übrig. Ein weiterer Schnitt teilt den Rest in zwei Einheitsquadrate.

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

Das Startrechteck ist bereits ein Quadrat.

So gehst du vor

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

Hinweis 1

Ein Rechteck lässt sich lösen, indem du es in zwei kleinere Rechtecke teilst und deren beste Antworten kombinierst.

Hinweis 2

Probiere jeden möglichen horizontalen und vertikalen Schnitt aus, um das Minimum zu finden.

Hinweis 3

Memoization oder eine Tabelle hilft, weil viele Teilrechtecke mehrfach vorkommen.

Erwartete Komplexität

Zeit O(h*w*(h+w)), zusätzlicher Speicher O(h*w)

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.