Bài 28.2: Bài toán người du lịch (TSP) với DP Bitmask

Chào mừng các bạn đến với bài viết tiếp theo trong series về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau đối mặt với một trong những bài toán kinh điển và "khó nhằn" nhất trong lĩnh vực khoa học máy tính: Bài toán người du lịch, hay còn gọi là Traveling Salesperson Problem (TSP).

TSP nổi tiếng vì sự đơn giản trong cách phát biểu nhưng lại vô cùng phức tạp khi tìm kiếm lời giải tối ưu. Chúng ta sẽ khám phá một kỹ thuật mạnh mẽ để giải quyết bài toán này cho các trường hợp có kích thước nhỏ: Lập trình động (Dynamic Programming) kết hợp với Bitmask.

Bài toán người du lịch (TSP) là gì?

Hãy tưởng tượng bạn là một người bán hàng, cần đi thăm tất cả các thành phố trong danh sách của mình, mỗi thành phố chỉ một lần, và cuối cùng phải quay trở lại thành phố xuất phát. Mục tiêu của bạn là tìm ra lộ trình đi sao cho tổng quãng đường di chuyển là ngắn nhất.

Formal hơn, bài toán được phát biểu như sau: Cho một tập hợp $N$ thành phố và chi phí (hoặc khoảng cách) để đi từ bất kỳ thành phố nào đến bất kỳ thành phố khác. Hãy tìm một chu trình đi qua tất cả các thành phố đúng một lần và quay về thành phố ban đầu, sao cho tổng chi phí của chu trình là nhỏ nhất.

Chi phí giữa hai thành phố có thể được biểu diễn dưới dạng ma trận kề cost[i][j], là chi phí đi từ thành phố i đến thành phố j. Nếu đồ thị là vô hướng, cost[i][j] = cost[j][i].

Tại sao TSP lại khó? Thử sức với vét cạn

Nghe có vẻ đơn giản đúng không? Tại sao lại nói nó khó?

Thử suy nghĩ theo cách đơn giản nhất: liệt kê tất cả các lộ trình có thể, tính tổng chi phí của từng lộ trình và chọn lộ trình có chi phí nhỏ nhất.

Nếu có $N$ thành phố, giả sử chúng ta bắt đầu từ thành phố 0.

Thành phố thứ hai có thể là bất kỳ trong $N-1$ thành phố còn lại.
Thành phố thứ ba có thể là bất kỳ trong $N-2$ thành phố còn lại (trừ thành phố 0 và thành phố thứ hai).
...
Thành phố cuối cùng là thành phố còn lại duy nhất.

Số lượng các lộ trình khác nhau (bắt đầu từ một thành phố cụ thể và đi qua tất cả các thành phố còn lại trước khi quay về) là $(N-1)!$ (giai thừa của $N-1$).

Đây là con số tăng trưởng cực kỳ nhanh:

N = 4: 3! = 6 lộ trình
N = 10: 9! = 362,880 lộ trình
N = 15: 14! = 87,178,291,200 lộ trình
N = 20: 19! ≈ $1.2 \times 10^{17}$ lộ trình

Với $N$ chỉ khoảng 20, số lượng lộ trình đã vượt quá khả năng tính toán của ngay cả những siêu máy tính hiện đại trong một khoảng thời gian hợp lý. Đây chính là lý do tại sao TSP là một bài toán NP-hard. Phương pháp vét cạn hoàn toàn không khả thi cho các trường hợp $N$ đủ lớn.

Hướng tiếp cận: Lập trình động (Dynamic Programming)

Khi vét cạn không hiệu quả và bài toán có cấu trúc tối ưu con (tức là lời giải tối ưu cho bài toán lớn chứa đựng lời giải tối ưu cho các bài toán con) và các bài toán con chồng chéo, chúng ta thường nghĩ đến Lập trình động (Dynamic Programming - DP).

Ý tưởng của DP là lưu trữ kết quả của các bài toán con để tránh tính toán lặp lại. Nhưng làm thế nào để định nghĩa "bài toán con" trong TSP?

Một bài toán con cần đủ thông tin để có thể mở rộng ra thành lời giải cho bài toán lớn hơn. Đối với TSP, nếu chúng ta đang ở một thành phố u, để quyết định đi tiếp đến thành phố nào v, chúng ta cần biết:

Chúng ta đã đi qua những thành phố nào rồi? (Để đảm bảo đi qua tất cả và mỗi thành phố một lần)
Thành phố hiện tại chúng ta đang ở là thành phố nào? (Để biết chi phí đi đến thành phố tiếp theo)

Nếu chỉ biết thành phố hiện tại u, chúng ta không biết mình đã thăm những đâu, nên không thể đảm bảo lộ trình cuối cùng đi qua tất cả các thành phố chưa thăm.

Đây là lúc Bitmask tỏa sáng!

Sức mạnh của Bitmask trong DP cho TSP

Bitmask là một kỹ thuật sử dụng các bit trong một số nguyên để biểu diễn một tập hợp hoặc một trạng thái. Với $N$ thành phố, chúng ta có thể dùng một số nguyên có $N$ bit để biểu diễn tập hợp các thành phố đã được thăm.

Bit thứ $i$ (tính từ phải sang, bắt đầu từ 0) bằng 1: Thành phố $i$ đã được thăm.
Bit thứ $i$ bằng 0: Thành phố $i$ chưa được thăm.

Ví dụ với $N=4$ thành phố (đánh số từ 0 đến 3):

Mask 0000 (binary) = 0 (decimal): Chưa thăm thành phố nào.
Mask 0001 (binary) = 1 (decimal): Đã thăm thành phố 0.
Mask 0010 (binary) = 2 (decimal): Đã thăm thành phố 1.
Mask 1011 (binary) = 11 (decimal): Đã thăm thành phố 0, 1, và 3.
Mask 1111 (binary) = 15 (decimal): Đã thăm tất cả 4 thành phố.

Tổng số trạng thái (mask) có thể có là $2^N$.

Bây giờ, chúng ta có thể định nghĩa trạng thái cho DP:

dp[mask][u] : Chi phí nhỏ nhất để đi từ thành phố bắt đầu (giả sử là thành phố 0) qua tất cả các thành phố được biểu diễn bởi mask, và dừng lại ở thành phố u.

Để trạng thái này có ý nghĩa, thành phố u phải là một trong các thành phố đã được thăm trong mask. Tức là, bit thứ u trong mask phải bằng 1.

Kích thước của bảng DP sẽ là $2^N \times N$.

Xây dựng DP: Cơ sở và Chuyển trạng thái

1. Cơ sở (Base Case)

Giả sử chúng ta luôn bắt đầu từ thành phố 0. Lộ trình ban đầu chỉ bao gồm duy nhất thành phố 0. Trạng thái này được biểu diễn bởi mask mà chỉ có bit thứ 0 là 1, tức là 1 << 0 hay 1. Thành phố hiện tại đang dừng là 0. Chi phí để đạt được trạng thái này là 0.

Vậy, cơ sở của DP là: dp[1 << 0][0] = 0

Tất cả các giá trị dp[mask][u] khác ban đầu sẽ được gán bằng một giá trị vô cùng lớn (INF) để biểu diễn trạng thái không thể đạt được hoặc chưa được tính toán.

2. Chuyển trạng thái (Transitions)

Chúng ta sẽ xây dựng bảng DP một cách "từ dưới lên" hoặc "từ trái sang phải" dựa trên số lượng bit 1 trong mask (số lượng thành phố đã thăm), hoặc đơn giản là duyệt qua tất cả các mask theo thứ tự tăng dần.

Xét một trạng thái dp[mask][u], biểu thị chi phí nhỏ nhất để đến thành phố u sau khi đã thăm các thành phố trong mask. Giả sử giá trị này đã được tính toán và không phải INF.

Chúng ta muốn mở rộng lộ trình này bằng cách đi từ thành phố u đến một thành phố v chưa được thăm. Một thành phố v chưa được thăm nếu bit thứ v trong mask là 0. Tức là !((mask >> v) & 1).

Nếu đi từ u đến v, chúng ta sẽ chuyển sang một trạng thái mới:

Mask mới: mask | (1 << v) (thêm thành phố v vào tập hợp đã thăm).
Thành phố hiện tại mới: v.
Chi phí để đạt trạng thái mới thông qua lộ trình đi từ u là dp[mask][u] + cost[u][v].

Vì chúng ta muốn tìm chi phí nhỏ nhất, chúng ta sẽ cập nhật giá trị dp[mask | (1 << v)][v] bằng giá trị nhỏ nhất giữa giá trị hiện tại của nó và chi phí mới tính được:

dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + cost[u][v])

Quá trình chuyển trạng thái sẽ diễn ra như sau:

Duyệt qua tất cả các mask có thể, từ 1 đến (1 << N) - 1.
Với mỗi mask, duyệt qua tất cả các thành phố u từ 0 đến N-1.
- Kiểm tra xem thành phố u có thuộc tập hợp trong mask hay không ((mask >> u) & 1).
- Kiểm tra xem dp[mask][u] có phải là giá trị có thể đạt được hay không (khác INF).
- Nếu cả hai điều kiện trên đúng, duyệt qua tất cả các thành phố v từ 0 đến N-1.
  - Kiểm tra xem thành phố v không thuộc tập hợp trong mask hay không (!((mask >> v) & 1)).
  - Nếu điều kiện trên đúng và có đường đi từ u đến v (cost[u][v] khác INF và không phải là đường đi từ một thành phố đến chính nó nếu bài toán không cho phép), thực hiện cập nhật: dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + cost[u][v])

Thứ tự duyệt mask tăng dần đảm bảo rằng khi chúng ta tính toán dp[mask'][v], tất cả các giá trị dp[mask][u] mà mask là tập con của mask' đã được tính trước đó.

Tìm lời giải cuối cùng

Sau khi đã tính toán xong bảng DP cho tất cả các mask, đặc biệt là mask biểu diễn tất cả các thành phố đã được thăm, đó là mask (1 << N) - 1.

Trạng thái dp[(1 << N) - 1][i] cho biết chi phí nhỏ nhất để đi từ thành phố bắt đầu (thành phố 0) qua tất cả các thành phố và kết thúc tại thành phố i.

Để hoàn thành chu trình TSP, chúng ta cần đi từ thành phố cuối cùng i trở về thành phố bắt đầu (thành phố 0).

Lời giải cuối cùng sẽ là giá trị nhỏ nhất của dp[(1 << N) - 1][i] + cost[i][0] cho tất cả các thành phố i từ 1 đến $N-1$ (vì thành phố 0 là điểm bắt đầu và kết thúc, chúng ta cần đi qua tất cả các thành phố khác trước khi quay về 0).

Nếu bài toán yêu cầu bắt đầu tại thành phố bất kỳ và chỉ cần tìm chu trình nhỏ nhất đi qua tất cả các thành phố, việc bắt đầu tại 0 là đủ do tính chất chu trình của TSP (chi phí chu trình là như nhau dù bắt đầu từ đâu).

Độ phức tạp

Số trạng thái: Bảng DP có kích thước $2^N \times N$.
Chuyển trạng thái: Để tính một trạng thái, chúng ta duyệt qua tối đa $N$ thành phố tiếp theo.
Tổng thời gian: $O(2^N \times N \times N) = O(N^2 \times 2^N)$.
Bộ nhớ: $O(N \times 2^N)$ để lưu bảng DP.

So với $O(N!)$ của vét cạn, $O(N^2 \times 2^N)$ tốt hơn rất nhiều cho các giá trị $N$ nhỏ (khoảng $N \le 20$). Tuy nhiên, nó vẫn là hàm mũ và không khả thi cho $N$ lớn hơn (ví dụ $N=30$).

C++ Code Example

Hãy cùng triển khai giải thuật này bằng C++.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = 1e9; // Sử dụng giá trị đủ lớn cho vô cùng

int main() {
    // Tắt đồng bộ I/O để tăng tốc (tùy chọn, hữu ích trong các bài thi)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Số lượng thành phố
    cout << "Nhap so luong thanh pho (N <= 20 de thuat toan chay hop ly): ";
    cin >> N;

    if (N > 20) {
        cout << "N lon, thuat toan co the rat cham. Can nhac cac phuong phap xap xi hoac heuristic." << endl;
        // Có thể thoát hoặc tiếp tục với rủi ro thời gian
    }

    // Ma trận chi phí giữa các thành phố
    // adj_matrix[i][j] là chi phí đi từ i đến j
    vector<vector<int>> adj_matrix(N, vector<int>(N));

    cout << "Nhap ma tran chi phi (" << N << "x" << N << ", nhap -1 cho duong di khong kha thi):" << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> adj_matrix[i][j];
            if (adj_matrix[i][j] == -1) {
                adj_matrix[i][j] = INF; // Bien duong di khong kha thi thanh vo cung
            }
        }
    }

    // Bảng DP: dp[mask][u] = chi phi nho nhat den u sau khi tham cac thanh pho trong mask
    // Kich thuoc: 2^N x N
    vector<vector<int>> dp(1 << N, vector<int>(N, INF));

    // Base case: Bat dau tu thanh pho 0.
    // Mask chi co bit 0 set la (1 << 0) = 1.
    // Chi phi de o thanh pho 0 va chi tham moi thanh pho 0 la 0.
    dp[1][0] = 0;

    // Duyet qua tat ca cac mask
    // Mask cang lon tuc la da tham cang nhieu thanh pho
    for (int mask = 1; mask < (1 << N); ++mask) {
        // Duyet qua tat ca cac thanh pho hien tai (u)
        for (int u = 0; u < N; ++u) {
            // Neu thanh pho u co trong mask va dp[mask][u] co gia tri hop le (khac INF)
            if ((mask >> u) & 1 && dp[mask][u] != INF) {
                // Duyet qua tat ca cac thanh pho tiep theo (v)
                for (int v = 0; v < N; ++v) {
                    // Neu thanh pho v chua duoc tham (bit v trong mask la 0)
                    // va co duong di tu u den v (adj_matrix[u][v] khac INF)
                    if (!((mask >> v) & 1) && adj_matrix[u][v] != INF) {
                        // Tinh mask moi khi them thanh pho v
                        int next_mask = mask | (1 << v);

                        // Cap nhat chi phi toi thieu de den v voi next_mask
                        dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + adj_matrix[u][v]);
                    }
                }
            }
        }
    }

    // Tim ket qua cuoi cung
    // Ket qua la chi phi nho nhat de quay ve thanh pho bat dau (thanh pho 0)
    // sau khi da tham het tat ca cac thanh pho ((1 << N) - 1)
    // Duyet qua tat ca cac thanh pho i co the la diem dung cuoi cung truoc khi ve 0
    int min_cost = INF;
    int final_mask = (1 << N) - 1; // Mask voi tat ca cac bit = 1

    for (int i = 0; i < N; ++i) {
        // Neu co the dat duoc trang thai da tham het thanh pho va dung o i,
        // va co duong di tu i ve 0
        if (dp[final_mask][i] != INF && adj_matrix[i][0] != INF) {
             min_cost = min(min_cost, dp[final_mask][i] + adj_matrix[i][0]);
        }
    }

    // In ket qua
    if (min_cost == INF) {
        cout << "Khong co chu trinh TSP hop le ton tai." << endl;
    } else {
        cout << "Chi phi nho nhat cua chu trinh TSP la: " << min_cost << endl;
    }

    return 0;
}

Giải thích mã nguồn C++

Includes và Hằng số:
- iostream: Để nhập/xuất dữ liệu.
- vector: Sử dụng vector<vector<int>> cho ma trận kề và bảng DP.
- algorithm: Để sử dụng hàm min.
- limits: Để sử dụng numeric_limits<int>::max() hoặc định nghĩa INF. Chúng ta dùng 1e9 là một giá trị lớn đủ. Cần cẩn thận khi dùng INT_MAX trực tiếp vì INT_MAX + cost có thể gây tràn số; dùng INF / 2 hoặc một hằng số lớn như 1e9 thường an toàn hơn.
- INF: Một hằng số lớn để biểu diễn chi phí vô cùng hoặc trạng thái không thể đạt tới.
Đọc Input:
- Đọc số lượng thành phố N.
- Đọc ma trận chi phí adj_matrix[N][N]. Nếu nhập -1, chúng ta coi đó là đường đi không khả thi và gán nó bằng INF.
Khởi tạo DP Table:
- dp là một ma trận 2D có kích thước (1 << N) x N. 1 << N là $2^N$, số lượng các mask có thể có.
- Tất cả các giá trị trong dp được khởi tạo là INF.
Base Case:
- dp[1][0] = 0;: Đặt chi phí để "đạt được" trạng thái chỉ thăm thành phố 0 và đang ở thành phố 0 là 0. Mask 1 (binary 00...01) biểu thị chỉ có thành phố 0 được thăm.
Vòng lặp DP (Tính toán chuyển trạng thái):
- Vòng lặp ngoài for (int mask = 1; mask < (1 << N); ++mask): Duyệt qua tất cả các mask có thể, từ 1 đến $2^N - 1$. Thứ tự duyệt này quan trọng để đảm bảo các bài toán con nhỏ hơn (mask ít bit 1 hơn) được tính trước khi các bài toán lớn hơn (mask nhiều bit 1 hơn) phụ thuộc vào chúng.
- Vòng lặp giữa for (int u = 0; u < N; ++u): Duyệt qua tất cả các thành phố u có thể là thành phố hiện tại trong trạng thái dp[mask][u].
- if ((mask >> u) & 1 && dp[mask][u] != INF): Kiểm tra hai điều kiện:
  - (mask >> u) & 1: Bit thứ u của mask có bằng 1 không? Tức là, thành phố u có thuộc tập hợp các thành phố trong mask không?
  - dp[mask][u] != INF: Trạng thái dp[mask][u] có thể đạt được với chi phí hữu hạn không? (Đảm bảo chúng ta chỉ mở rộng từ các trạng thái hợp lệ).
- Vòng lặp trong for (int v = 0; v < N; ++v): Duyệt qua tất cả các thành phố v có thể là thành phố tiếp theo.
- if (!((mask >> v) & 1) && adj_matrix[u][v] != INF): Kiểm tra hai điều kiện:
  - !((mask >> v) & 1): Bit thứ v của mask có bằng 0 không? Tức là, thành phố v chưa thuộc tập hợp các thành phố trong mask?
  - adj_matrix[u][v] != INF: Có đường đi hợp lệ từ u đến v không?
- int next_mask = mask | (1 << v);: Tạo mask mới bằng cách bật bit thứ v trong mask hiện tại. Đây là mask của trạng thái mới sau khi thăm thành phố v.
- dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + adj_matrix[u][v]);: Cập nhật giá trị của trạng thái dp[next_mask][v]. So sánh chi phí hiện tại để đạt trạng thái này với chi phí mới dp[mask][u] + adj_matrix[u][v] (đi từ trạng thái (mask, u) đến (next_mask, v)). Chọn giá trị nhỏ nhất.
Tìm kết quả cuối cùng:
- Sau khi tất cả các trạng thái đã được tính, chúng ta cần tìm chi phí nhỏ nhất để hoàn thành chu trình bằng cách quay về thành phố bắt đầu (thành phố 0).
- final_mask = (1 << N) - 1;: Đây là mask mà tất cả $N$ bit đều bằng 1, biểu thị tất cả các thành phố đã được thăm.
- Vòng lặp for (int i = 0; i < N; ++i): Duyệt qua tất cả các thành phố i có thể là thành phố cuối cùng trong lộ trình trước khi quay về 0.
- if (dp[final_mask][i] != INF && adj_matrix[i][0] != INF): Kiểm tra xem có thể đạt được trạng thái thăm hết các thành phố và dừng ở i không, và có đường đi từ i về 0 không.
- min_cost = min(min_cost, dp[final_mask][i] + adj_matrix[i][0]);: Cập nhật chi phí nhỏ nhất bằng cách cộng chi phí đến thành phố cuối i (dp[final_mask][i]) với chi phí quay về thành phố 0 (adj_matrix[i][0]).
- min_cost cuối cùng sẽ là chi phí nhỏ nhất của chu trình TSP.
In kết quả: In min_cost hoặc thông báo nếu không có chu trình hợp lệ (khi min_cost vẫn là INF).

Bài tập ví dụ:

Mảng Con Chẵn Lẻ

Trong một buổi thực hành nấu ăn, FullHouse Dev được đầu bếp giao cho một thử thách thú vị. Họ phải tìm cách phân tích các phần nguyên liệu sao cho số lượng nguyên liệu có khối lượng chẵn và lẻ gram cân bằng nhau.

Bài toán

FullHouse Dev được cung cấp một mảng $A$ gồm $N$ giá trị nguyên dương. Một mảng con của mảng này được gọi là mảng con Chẵn-Lẻ nếu số lượng số lẻ trong mảng con bằng với số lượng số chẵn trong mảng con đó.

Nhiệm vụ của nhóm là tìm ra số lượng mảng con Chẵn-Lẻ có thể tạo được từ mảng đã cho.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $N$ - kích thước của mảng.
Dòng thứ hai chứa $N$ số nguyên dương cách nhau bởi dấu cách, biểu diễn các phần tử của mảng $A$.

OUTPUT FORMAT:

In ra một số nguyên duy nhất, biểu thị số lượng mảng con Chẵn-Lẻ có thể tạo được.

Ràng buộc:

$1 \leq N \leq 10^5$
$1 \leq A[i] \leq 10^9$

Ví dụ

INPUT

4
1 2 1 2

OUTPUT

Giải thích

Gọi $A[i,j]$ là mảng con của $A$ bắt đầu từ chỉ số $i$ và kết thúc ở chỉ số $j$.

Có bốn mảng con thỏa mãn số lượng số chẵn bằng số lượng số lẻ:

$A[1,2]$ chứa một số lẻ và một số chẵn
$A[2,3]$ chứa một số lẻ và một số chẵn
$A[3,4]$ chứa một số lẻ và một số chẵn
$A[1,4]$ chứa hai số lẻ và hai số chẵn Chào bạn, đây là hướng dẫn giải cho bài toán "Mảng Con Chẵn Lẻ" theo yêu cầu không cung cấp code hoàn chỉnh:

Phân tích bài toán: Bạn cần đếm số lượng mảng con có số lượng phần tử chẵn bằng số lượng phần tử lẻ.
Biến đổi bài toán:
- Hãy xem xét mỗi phần tử trong mảng gốc. Nếu nó là số lẻ, ta gán cho nó giá trị +1. Nếu nó là số chẵn, ta gán cho nó giá trị -1.
- Sau khi biến đổi, mảng con gốc có số lượng số lẻ bằng số lượng số chẵn khi và chỉ khi tổng các giá trị trong mảng con đã biến đổi bằng 0.
- Bài toán gốc trở thành: Đếm số lượng mảng con trong mảng đã biến đổi mà có tổng bằng 0.
Áp dụng Kỹ thuật Tổng Tiền Tố (Prefix Sum):
- Bài toán đếm mảng con có tổng bằng một giá trị cố định (ở đây là 0) là một bài toán kinh điển có thể giải hiệu quả bằng tổng tiền tố.
- Tính mảng tổng tiền tố P, trong đó P[i] là tổng của các phần tử từ đầu mảng biến đổi đến chỉ số i-1 (hoặc P[0]=0 và P[i] là tổng đến chỉ số i tùy theo quy ước).
- Tổng của một mảng con từ chỉ số i đến j trong mảng biến đổi chính là P[j+1] - P[i] (sử dụng quy ước P[k] là tổng k phần tử đầu tiên, P[0]=0).
- Ta cần tìm các cặp chỉ số (i, j) sao cho P[j+1] - P[i] = 0, tức là P[j+1] = P[i].
Sử dụng Bảng Băm (Hash Map / Dictionary):
- Duyệt qua mảng tổng tiền tố (hoặc tính tổng tiền tố động khi duyệt mảng gốc).
- Sử dụng một bảng băm để lưu trữ tần suất xuất hiện của mỗi giá trị tổng tiền tố đã gặp cho đến vị trí hiện tại.
- Khởi tạo bảng băm với tổng_tiền_tố_hiện_tại = 0 với tần suất là 1. Điều này là để tính các mảng con bắt đầu từ chỉ số 0.
- Khi duyệt qua mảng và tính được tổng tiền tố current_sum tại vị trí k, nếu giá trị current_sum đã xuất hiện m lần trước đó (tại các vị trí i_1, i_2, ..., i_m), thì có m mảng con kết thúc tại vị trí k-1 (trong mảng biến đổi) có tổng bằng 0. Các mảng con này bắt đầu tại các vị trí i_1, i_2, ..., i_m.
- Thêm m vào tổng số lượng mảng con Chẵn-Lẻ.
- Sau đó, tăng tần suất của current_sum trong bảng băm lên 1.
Các bước thực hiện:
- Tạo mảng mới (hoặc xử lý trực tiếp) bằng cách thay thế số lẻ bằng 1, số chẵn bằng -1.
- Khởi tạo count = 0, current_sum = 0.
- Khởi tạo một bảng băm freq_map và đặt freq_map[0] = 1.
- Duyệt qua từng phần tử của mảng đã biến đổi từ trái sang phải:
  - Cập nhật current_sum bằng cách cộng giá trị phần tử hiện tại.
  - Kiểm tra xem current_sum có tồn tại trong freq_map không.
  - Nếu có, lấy tần suất của current_sum từ freq_map và cộng vào count.
  - Tăng tần suất của current_sum trong freq_map lên 1.
- Kết quả cuối cùng là giá trị của count.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.