Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Cut a Rectangle Into Squares

Find the fewest straight cuts needed to produce only squares.

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

Ví dụ

Ví dụ 1
Đầu vào:
height = 2
width = 3

Kết quả mong đợi:
expected = 2
Đầu vào:
long long height = 2;
long long width = 3;

Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long height = 2;
long width = 3;

Kết quả mong đợi:
long expected = 2;

Giải thích

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

Ví dụ 2
Đầu vào:
height = 4
width = 4

Kết quả mong đợi:
expected = 0
Đầu vào:
long long height = 4;
long long width = 4;

Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long height = 4;
long width = 4;

Kết quả mong đợi:
long expected = 0;

Giải thích

The starting rectangle is already a square.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

Memoization or a table is helpful because many subrectangles repeat.

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 954 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.