Cần giúp bài quy hoạch động

Cho một bảng số A gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình chữ nhật thành hai hình chữ
nhật riêng biệt. Cứ tiếp tục cắt cho ñến khi hình chữ nhật toàn bằng 1 hay toàn bằng 0. Hãy tìm cách cắt để được ít hình chữ nhật nhất mà các hình chữ nhật con có giá trị toàn bằng 1 hay toàn bằng 0.

Ví dụ: Bảng số 5×5 sau ñược chia thành 8 hình chữ nhật con.

0 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 0 0
0 0 1 0 0

2 Likes

Tìm cách để build từ thấp lên cao luôn là một cách tiếp cận tốt với dynamic programming.
Đối với bài này bắt đầu từ các ma trận nhỏ nhất 1x1, tìm cách merge với các ma trận khả dụng xung quanh nó để tìm ra cách lựa chọn tốt nhất. Đệ quy kết hợp vòng lặp. Lưu các lựa chọn tốt nhất thì bạn tự tìm cách, hình dung ra được phương pháp rồi thì chỉ work around chút thôi.

3 Likes

cảm ơn bạn! bạn hướng dẫn thuật toán cho mình nhé! giúp m với!

Bài này khá căng :smiley: cần nhiều test hơn.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?