fill(f, f + (1 << n), a[0]); // do phương pháp duyệt tập con bỏ qua tập rỗng
for (int mask = 0; mask < (1 << n); mask++) {
    for (int sub = mask; sub; sub = (sub - 1) & mask) f[mask] += a[sub];
}

Cài đặt

Với công thức truy hồi như trên, khi cài đặt, việc duyệt theo biến hay trước đều đúng. Tuy nhiên, mỗi cách làm có ưu/nhược điểm riêng nên ta sẽ tìm hiểu cả hai.

Cách 1

Ta sẽ duyệt theo biến trước:

vector sos(1 << n);
vector<vector> dp(1 << n, vector(n + 1));

for (int x = 0; x < (1 << n); x++) {
	dp[x][0] = a[x];
	for (int i = 0; i < n; i++) {
		dp[x][i + 1] = dp[x][i];
		if (x & (1 << i)) { dp[x][i + 1] += dp[x ^ (1 << i)][i]; }
	}
	sos[x] = dp[x][n];
}

Ưu điểm của cách cài đặt này là khi bắt đầu tính cho một bất kì, ta đã có kết quả của mọi trạng thái liên quan đến sub-masks của , do đó, cách này còn được gọi là “online” DP SoS. Điều này vô cùng hữu ích đối với những bài DP SoS có công thức tự gọi lại chính nó.

Tuy nhiên, cách làm này không thể tối ưu bộ nhớ xuống được.

Cách 2 (Tối ưu bộ nhớ)

Ta có thể đưa biến lên trước trong cách đặt trạng thái và chỉ duy trì dòng của bảng Quy hoạch động, hay thậm chí là dòng nếu ta duyệt các mask từ lớn đến nhỏ (ý tưởng tương tự DP Knapsack).

for (int k = 1; k <= n; k++)
    for (int mask = (1 << n) - 1; mask >= 0; mask--)
        if (mask & (1 << (k - 1))) sos[mask] += sos[mask ^ (1 << (k - 1))];

Để cài đặt ngắn gọn hơn nữa, ta còn có thể đưa ra nhận xét rằng đối với DP SoS, việc duyệt các mask từ nhỏ đến lớn cũng không làm sai kết quả. Hơn nữa, vì không còn cần phải đánh số dòng trên bảng QHĐ, ta có thể duyệt từ đến và coi trường hợp cơ sở là , sẽ thuật tiện hơn cho việc xử lý bitmask. Đến đây, ta đã có code DP SoS rất ngắn, dễ cài đặt, tối ưu bộ nhớ và hằng số thấp. Nhìn chung, cách làm này phổ biến hơn cách 1.

for (int k = 0; k < n; k++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask & (1 << k)) sos[mask] += sos[mask ^ (1 << k)];

SOS DP as N-Dimensional Prefix Sum

Trước khi tiếp tục, hãy xem lại tổng tiền tố 2D. Cho mảng \( A \) có kích thước \( n \times m \), mảng tổng tiền tố \( S \) được định nghĩa như sau: \[ S[i][j] = \sum_{a \leq i} \sum_{b \leq j} A[a][b] \] Phương pháp chuẩn sử dụng bao gồm loại trừ: \[ S[i][j] = S[i-1][j-1] + S[i-1][j] + S[i][j-1] – S[i-1][j-1] + A[i][j] \] Mặc dù phương pháp này hoạt động cho 2D, nó có một hạn chế đáng kể: khi số chiều tăng lên, số lượng các phép toán cần thêm hoặc bớt cũng tăng, làm cho việc tính toán trở nên không hiệu quả cho nhiều chiều.

// Initialize
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) { S[i][j] = A[i][j]; }
}

// Sweep along x-axis
for (int i = 1; i < n; i++) {
	for (int j = 0; j < m; j++) { S[i][j] += S[i - 1][j]; }
}

// Sweep along y-axis
for (int i = 0; i < n; i++) {
	for (int j = 1; j < m; j++) { S[i][j] += S[i][j - 1]; }
}

Phương pháp này tổng quát hóa cho các chiều lớn hơn.

Giả sử chúng ta muốn tính tổng tiền tố cho 4D. Chúng ta có thể tính toán điều này bằng cách quét dọc theo từng trục của 4D, tại một thời điểm:

Đầu tiên, quét dọc theo trục \( a \): \[ S[i][j][k][l] = \sum_{0 \leq a \leq i} A[a][j][k][l] \]

Sau khi quét dọc theo trục \( x \): \[ S[i][j][k][l] = \sum_{0 \leq a \leq i} S[a][j][k][l] \]

Tiếp theo, quét dọc theo trục \( b \): \[ S[i][j][k][l] = \sum_{0 \leq b \leq j} S[i][b][k][l] \]

Cuối cùng, sau khi quét dọc theo trục \( c \): \[ S[i][j][k][l] = \sum_{0 \leq c \leq k} S[i][j][c][l] \]

Nếu chúng ta mở rộng điều này sang các chiều, đây là những gì xảy ra: khi quét theo chỉ số \( i \)-th, \( S[i] \) chứa các giá trị mà \( A \) đã tính toán ở đó. Hơn nữa, các chỉ số đầu tiên là tọa độ mà chúng ta đang xem xét trong bài toán tìm kiếm.

Điều này cho thấy, khi chúng ta thêm một bit vào một lưới, thì bit đó là một tọa độ \( n \)-chiều, \( F(x) \) tương ứng với định nghĩa của một tổng tiền tố \( n \)-chiều.

Bằng cách quét theo từng chiều, chúng ta có thể tối ưu hóa DP mà đã được đề cập, chứng minh rằng SOS DP thực sự là một tổng tiền tố \( n \)-chiều.

F = A;

for (int i = 0; i < n; i++) {  // Sweep along the i-th axis
	for (int x = 0; x < (1 << n); x++) {
		if (x & (1 << i))  // If the i-th bit is set, accumulate
			F[x] += F[x ^ (1 << i)];
	}
}

¶ Tham khảo

• [USACO Guide] Siyong Huang, Aakash Gokhale – Sum over Subsets DP
• [Codeforces] usaxena95 – SOS Dynamic Programming
• [Codeforces] sidhant – Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution