<h2>Phân loại</h2><ul><li><strong>Quy hoạch động (DP)</strong> trên ma trận</li><li>Dạng: <strong>đếm số hình vuông toàn số 0</strong></li></ul><h2>Dấu hiệu nhận biết</h2><ul><li>Ma trận 0/1</li><li>Yêu cầu <strong>đếm số hình vuông không chứa 1</strong></li><li>Mỗi ô có thể là <strong>góc phải dưới của hình vuông</strong></li></ul><h2>Ý tưởng</h2><p>Gọi dp[i][j] là <strong>kích thước hình vuông lớn nhất</strong> có góc phải dưới tại (i, j)</p><ul><li>Nếu ô (i, j) = 1 → dp[i][j] = 0</li><li>Nếu ô (i, j) = 0: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1</li></ul><p>==>dp[i][j] : số hình vuông kết thúc tại (i, j)</p><h2>Thuật toán</h2><ul><li>Duyệt toàn bộ ma trận</li><li>Tính dp theo công thức trên</li><li>Cộng tất cả dp[i][j] lại</li></ul><h2>Kết luận</h2><ul><li>Tổng số cách chọn = <strong>tổng dp[i][j] với mọi i, j</strong></li><li>Độ phức tạp: <strong>O(M × N)</strong></li></ul><p> </p>