Đề bài
Ở mỗi lượt, chọn một hình chữ nhật và cắt dọc theo một đường thẳng song song với một cạnh, chia nó thành hai hình chữ nhật có chiều dài các cạnh là số nguyên dương. Tiếp tục cho đến khi mọi mảnh đều là hình vuông. Các hình vuông có thể có kích thước khác nhau. Đếm số lần cắt, không phải số mảnh.
Cài đặt hàm rectangle_cutting(height, width).
Đầu vào
height: Chiều cao của hình chữ nhật ban đầu.
width: Chiều rộng của hình chữ nhật ban đầu.
Đầu ra
Trả về số lần cắt ít nhất.
Ràng buộc
1 ≤ height, width ≤ 500. Xoay hình không làm thay đổi đáp án.
Ví dụ
Đầu vào:
width = 3
height = 2
Kết quả mong đợi:
expected = 2Đầu vào:
long long width = 3;
long long height = 2;
Kết quả mong đợi:
long long expected = 2;Đầu vào:
long width = 3;
long height = 2;
Kết quả mong đợi:
long expected = 2;Giải thích
Cắt ra một hình vuông 2 × 2, còn lại một hình chữ nhật 2 × 1. Thêm một lần cắt nữa chia phần còn lại thành hai hình vuông đơn vị.
Đầu vào:
width = 4
height = 4
Kết quả mong đợi:
expected = 0Đầu vào:
long long width = 4;
long long height = 4;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long width = 4;
long height = 4;
Kết quả mong đợi:
long expected = 0;Giải thích
Hình chữ nhật ban đầu đã là hình vuông.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một hình chữ nhật có thể giải bằng cách chia thành hai hình chữ nhật nhỏ hơn rồi ghép đáp án tốt nhất của chúng.
Gợi ý 2
Thử mọi đường cắt ngang và dọc để tìm số lần cắt ít nhất.
Gợi ý 3
Memoization hoặc bảng DP rất hữu ích vì nhiều hình chữ nhật con bị lặp lại.
Độ phức tạp mong đợi
thời gian O(h*w*(h+w)), bộ nhớ phụ O(h*w)
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.