Bài 5.3: Kỹ thuật ghi nhớ (Memoization) và tối ưu đệ quy

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một kỹ thuật cực kỳ mạnh mẽ giúp cải thiện đáng kể hiệu suất của các giải thuật đệ quy: Kỹ thuật ghi nhớ, hay còn gọi là Memoization.

Đệ quy là một công cụ thanh lịch để giải quyết nhiều bài toán bằng cách chia chúng thành các bài toán con nhỏ hơn. Tuy nhiên, đệ quy "ngây thơ" (naive recursion) thường ẩn chứa một điểm yếu chí mạng: tính toán lặp đi lặp lại cùng một bài toán con. Đây chính là lúc Memoization toả sáng!

Vấn đề của Đệ quy "Ngây Thơ": Bài toán con gối nhau

Hãy cùng xem xét một ví dụ kinh điển: dãy Fibonacci. Dãy Fibonacci được định nghĩa như sau:

$F(0) = 0$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2)$ với $n > 1$

Một cách tự nhiên để tính $F(n)$ bằng đệ quy là trực tiếp áp dụng định nghĩa:

#include <iostream>

// Hàm tính số Fibonacci thứ n bằng đệ quy ngây thơ
long long fib_naive(int n) {
    if (n <= 1) {
        return n; // Base cases: F(0) = 0, F(1) = 1
    }
    // Recursive step: F(n) = F(n-1) + F(n-2)
    return fib_naive(n - 1) + fib_naive(n - 2);
}

int main() {
    int n = 10;
    std::cout << "So Fibonacci thu " << n << " (de quy ngay tho) la: " << fib_naive(n) << std::endl; // Output: 55

    n = 20;
    std::cout << "So Fibonacci thu " << n << " (de quy ngay tho) la: " << fib_naive(n) << std::endl; // Output: 6765

    // Thu voi n lon hon, ban se thay no rat cham!
    // n = 40;
    // std::cout << "So Fibonacci thu " << n << " (de quy ngay tho) la: " << fib_naive(n) << std::endl; 

    return 0;
}

Code này nhìn có vẻ đúng và đơn giản, nhưng hãy thử chạy nó với giá trị $n$ đủ lớn (ví dụ $n=40$). Bạn sẽ thấy nó rất chậm hoặc thậm chí không kịp hoàn thành. Tại sao vậy?

Hãy xem cây đệ quy cho fib_naive(4):

          fib(4)
         /      \
      fib(3)    fib(2)
     /    \     /    \
  fib(2) fib(1) fib(1) fib(0)
 /    \
fib(1) fib(0)

Bạn có thấy điều gì lặp lại không?

fib(2) được tính hai lần.
fib(1) được tính ba lần.
fib(0) được tính hai lần.

Khi $n$ lớn hơn, cùng một giá trị Fibonacci (ví dụ $F(k)$ cho một $k$ nào đó) sẽ được tính toán lặp đi lặp lại vô số lần tại các nhánh khác nhau của cây đệ quy. Điều này dẫn đến độ phức tạp thời gian theo cấp số mũ, xấp xỉ $O(2^n)$. Cây đệ quy phát triển rất nhanh, và phần lớn công việc là tính lại những thứ đã tính rồi. Đây chính là hiện tượng bài toán con gối nhau (overlapping subproblems).

Kỹ thuật ghi nhớ (Memoization): Lưu trữ và Tái sử dụng

Memoization là một kỹ thuật tối ưu hóa được sử dụng chủ yếu để tăng tốc độ tính toán bằng cách lưu trữ kết quả của các lời gọi hàm "đắt đỏ" và trả về kết quả đã lưu khi cùng một đầu vào xuất hiện lại.

Ý tưởng rất đơn giản:

Khi một hàm đệ quy được gọi với một đầu vào cụ thể, trước khi thực sự tính toán kết quả, hãy kiểm tra xem kết quả cho đầu vào này đã được tính và lưu trữ chưa.
Nếu có, trả về ngay kết quả đã lưu thay vì tính toán lại.
Nếu chưa, thực hiện tính toán như bình thường.
Sau khi tính toán xong, lưu trữ kết quả này vào bộ nhớ (gọi là "memo table" hoặc "cache") trước khi trả về.

Bằng cách này, mỗi bài toán con duy nhất chỉ cần được tính toán một lần duy nhất.

Áp dụng Memoization cho Dãy Fibonacci

Để áp dụng Memoization cho bài toán Fibonacci, chúng ta cần một nơi để lưu trữ kết quả đã tính. Một mảng (hoặc std::vector trong C++) là lựa chọn tốt cho bài toán này vì các chỉ số $n$ là các số nguyên liên tiếp bắt đầu từ 0. Chúng ta sẽ sử dụng một giá trị đặc biệt (ví dụ: -1) để đánh dấu rằng kết quả cho một chỉ số nào đó chưa được tính.

#include <iostream>
#include <vector> // Cần để sử dụng std::vector

// Khai báo một vector toàn cục hoặc truyền vào hàm
// Sử dụng -1 để chỉ ra rằng giá trị chưa được tính
std::vector<long long> memo;

// Hàm tính số Fibonacci thứ n bằng đệ quy có ghi nhớ (Memoization)
long long fib_memo(int n) {
    // Base cases vẫn giữ nguyên
    if (n <= 1) {
        return n;
    }

    // Bước 1: Kiểm tra xem kết quả đã được lưu trữ chưa
    // Kích thước của memo cần đủ lớn để chứa F(n), nên cần n+1 phần tử
    // Đảm bảo memo đã được resize phù hợp trước khi gọi hàm lần đầu
    if (memo[n] != -1) {
        return memo[n]; // Bước 2: Trả về kết quả đã lưu
    }

    // Bước 3: Nếu chưa, tính toán kết quả bằng đệ quy
    long long result = fib_memo(n - 1) + fib_memo(n - 2);

    // Bước 4: Lưu trữ kết quả trước khi trả về
    memo[n] = result;

    return result;
}

int main() {
    int n = 40; // Thử với giá trị lớn hơn

    // Chuẩn bị memo table: kích thước n+1 và khởi tạo tất cả bằng -1
    memo.assign(n + 1, -1); 
    // Hoặc: memo.resize(n + 1, -1);

    std::cout << "So Fibonacci thu " << n << " (de quy co ghi nho) la: " << fib_memo(n) << std::endl; // Output: 102334155 (rất nhanh)

    n = 50; // Thử với giá trị lớn hơn nữa
    memo.assign(n + 1, -1);
    std::cout << "So Fibonacci thu " << n << " (de quy co ghi nho) la: " << fib_memo(n) << std::endl; // Output: 12586269025 (vẫn nhanh)

    return 0;
}

Giải thích code Memoization cho Fibonacci:

Chúng ta sử dụng std::vector<long long> memo để lưu trữ các giá trị Fibonacci đã tính. Kích thước của vector này cần là $n+1$ để có thể lưu trữ từ $F(0)$ đến $F(n)$.
Vector được khởi tạo với giá trị -1. Giá trị này không thể là kết quả của hàm fib cho $n \ge 0$, nên chúng ta dùng nó làm "cờ" để báo hiệu rằng kết quả cho chỉ số đó chưa được tính.
Trong hàm fib_memo(n), trước khi gọi đệ quy, chúng ta kiểm tra if (memo[n] != -1). Nếu điều kiện này đúng, nghĩa là kết quả cho fib(n) đã được tính toán ở một lời gọi đệ quy trước đó và lưu vào memo[n]. Chúng ta chỉ việc trả về giá trị này. Đây chính là mấu chốt của Memoization!
Nếu memo[n] vẫn là -1, chúng ta tiến hành tính toán result = fib_memo(n - 1) + fib_memo(n - 2) như bình thường.
Quan trọng: Sau khi có được kết quả result, chúng ta lưu nó vào memo[n] trước khi trả về. Lần sau, khi fib_memo(n) được gọi lại (từ nhánh khác của cây đệ quy chẳng hạn), nó sẽ tìm thấy kết quả đã lưu và không cần tính toán lại nữa.

Với Memoization, cây đệ quy trở nên "mỏng" đi rất nhiều. Mỗi giá trị $F(k)$ cho $0 \le k \le n$ chỉ được tính toán đúng một lần. Các lần truy cập tiếp theo chỉ là tra cứu trong mảng memo, là thao tác $O(1)$.

Độ phức tạp thời gian: Mỗi giá trị từ $F(0)$ đến $F(n)$ được tính một lần duy nhất. Có $n+1$ giá trị cần tính. Mỗi phép tính (sau khi kiểm tra memo) chỉ mất thời gian hằng số (một phép cộng). Do đó, độ phức tạp thời gian giảm từ $O(2^n)$ xuống còn $O(n)$.
Độ phức tạp không gian: Chúng ta cần $O(n)$ không gian để lưu trữ memo table. Ngoài ra còn có không gian cho stack đệ quy, trong trường hợp này cũng là $O(n)$ ở trường hợp xấu nhất. Tổng cộng là $O(n)$.

Đây là sự cải thiện khổng lồ về hiệu suất!

Ví dụ khác: Bài toán Đổi tiền (Minimum Coin Change)

Hãy xét một bài toán khác cũng thường được giải bằng đệ quy và có bài toán con gối nhau: Tìm số lượng đồng xu ít nhất để tạo thành một tổng tiền cho trước, với các mệnh giá đồng xu có sẵn.

Ví dụ: Các đồng xu có mệnh giá {1, 2, 5}. Tổng tiền cần đổi là 11.

11 = 5 + 5 + 1 (3 xu)
11 = 5 + 2 + 2 + 2 (4 xu)
11 = 2 + 2 + 2 + 2 + 2 + 1 (6 xu)
... Số lượng ít nhất là 3 xu (5+5+1).

Định nghĩa bài toán con: minCoins(amount) là số lượng đồng xu ít nhất để đổi thành amount.

minCoins(0) = 0 (không cần xu nào để có tổng 0)
minCoins(amount) = 1 + min(minCoins(amount - coin)) cho tất cả các coin trong tập mệnh giá sao cho amount - coin >= 0. Chúng ta lấy giá trị nhỏ nhất trong tất cả các khả năng.
Nếu không thể đổi được amount bằng các đồng xu, kết quả là "vô cực" (hoặc một giá trị rất lớn).

Đệ quy "ngây thơ" cho bài toán này:

#include <iostream>
#include <vector>
#include <algorithm> // Cần cho std::min

// Hàm tính số đồng xu ít nhất bằng đệ quy ngây thơ
int minCoins_naive(int amount, const std::vector<int>& coins) {
    // Base case 1: Nếu tổng tiền bằng 0, cần 0 đồng xu
    if (amount == 0) {
        return 0;
    }

    // Base case 2: Nếu tổng tiền âm, không thể đổi được, trả về một giá trị lớn (vô cực)
    if (amount < 0) {
        return 1e9; // Sử dụng một số đủ lớn làm "vô cực"
    }

    int min_count = 1e9; // Khởi tạo số lượng ít nhất là vô cực

    // Lặp qua từng loại đồng xu
    for (int coin : coins) {
        // Chỉ xét nếu mệnh giá đồng xu không vượt quá tổng tiền còn lại
        if (amount >= coin) {
            // Tính số đồng xu cần thiết cho tổng tiền còn lại sau khi dùng 1 đồng xu hiện tại
            int remaining_coins = minCoins_naive(amount - coin, coins);

            // Nếu tổng tiền còn lại có thể đổi được (không phải vô cực)
            if (remaining_coins != 1e9) {
                // Cập nhật số lượng đồng xu ít nhất: 1 (đồng xu hiện tại) + số đồng xu cho phần còn lại
                min_count = std::min(min_count, 1 + remaining_coins);
            }
        }
    }

    return min_count; // Trả về số lượng ít nhất tìm được
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;

    int result = minCoins_naive(amount, coins);

    if (result == 1e9) {
        std::cout << "Khong the doi tien cho tong " << amount << std::endl;
    } else {
        std::cout << "So dong xu it nhat de doi tong " << amount << " (de quy ngay tho) la: " << result << std::endl; // Output: 3
    }

    // Thử với tổng tiền lớn hơn, bạn sẽ thấy nó chậm

    return 0;
}

Tương tự như Fibonacci, hàm minCoins_naive(amount, coins) sẽ tính toán lặp đi lặp lại số lượng đồng xu cho cùng một amount trung gian. Ví dụ, để tính minCoins(10) bằng đồng xu {1, 2, 5}:

Dùng xu 5 trước: cần 1 + minCoins(5)
Dùng xu 2 trước: cần 1 + minCoins(8) -> sau đó có thể dùng xu 5: 1 + 1 + minCoins(3) -> dùng xu 2, dùng xu 1, ... -> cũng gọi đến minCoins(5)
Dùng xu 1 trước: cần 1 + minCoins(9) -> ...

Bài toán minCoins(5) sẽ được giải nhiều lần ở các nhánh khác nhau. Cấu trúc này lại là bài toán con gối nhau.

Bây giờ, chúng ta sẽ áp dụng Memoization:

#include <iostream>
#include <vector>
#include <algorithm> // Cần cho std::min
#include <climits>   // Cần cho INT_MAX (hoặc dùng 1e9)

// Khai báo memo table
std::vector<int> memo_coins;

// Hàm tính số đồng xu ít nhất bằng đệ quy có ghi nhớ (Memoization)
int minCoins_memo(int amount, const std::vector<int>& coins) {
    // Base case 1: Tổng tiền bằng 0
    if (amount == 0) {
        return 0;
    }

    // Base case 2: Tổng tiền âm (trường hợp không thể đổi được) - giữ nguyên
    if (amount < 0) {
        return INT_MAX; // Sử dụng INT_MAX từ <climits> hoặc 1e9
    }

    // Bước 1: Kiểm tra xem kết quả đã được lưu trữ chưa
    // Kích thước của memo cần đủ lớn cho amount, cần amount + 1 phần tử
    // Sử dụng INT_MAX (hoặc 1e9) làm giá trị "chưa tính" và "không thể đổi được"
    if (memo_coins[amount] != INT_MAX) { // Lưu ý: So sánh với INT_MAX/1e9
        return memo_coins[amount]; // Bước 2: Trả về kết quả đã lưu
    }

    int min_count = INT_MAX; // Khởi tạo số lượng ít nhất là vô cực

    // Lặp qua từng loại đồng xu
    for (int coin : coins) {
        // Chỉ xét nếu mệnh giá đồng xu không vượt quá tổng tiền còn lại
        if (amount >= coin) { // Điều kiện này có thể bỏ qua vì amount - coin < 0 sẽ xử lý ở base case
            // Tính số đồng xu cần thiết cho tổng tiền còn lại
            int remaining_coins = minCoins_memo(amount - coin, coins);

            // Nếu tổng tiền còn lại có thể đổi được (không phải vô cực)
            if (remaining_coins != INT_MAX) { // Lưu ý: So sánh với INT_MAX/1e9
                // Cập nhật số lượng đồng xu ít nhất
                min_count = std::min(min_count, 1 + remaining_coins);
            }
        }
    }

    // Bước 4: Lưu trữ kết quả trước khi trả về
    memo_coins[amount] = min_count;

    return min_count; // Trả về số lượng ít nhất tìm được
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 100; // Thử với tổng tiền lớn hơn

    // Chuẩn bị memo table: kích thước amount + 1 và khởi tạo tất cả bằng INT_MAX
    memo_coins.assign(amount + 1, INT_MAX);
    // Hoặc: memo_coins.resize(amount + 1, INT_MAX);

    int result = minCoins_memo(amount, coins);

    if (result == INT_MAX) { // Kiểm tra kết quả cuối cùng
        std::cout << "Khong the doi tien cho tong " << amount << std::endl;
    } else {
        std::cout << "So dong xu it nhat de doi tong " << amount << " (de quy co ghi nho) la: " << result << std::endl; // Kết quả nhanh chóng
    }

    return 0;
}

Giải thích code Memoization cho Đổi tiền:

Chúng ta dùng std::vector<int> memo_coins có kích thước amount + 1 để lưu kết quả cho các tổng tiền từ 0 đến amount.
Giá trị khởi tạo cho memo_coins là INT_MAX (hoặc một số rất lớn). Giá trị này đóng vai trò kép:
- Là "cờ" để chỉ ra rằng kết quả cho tổng tiền này chưa được tính.
- Là giá trị trả về khi không thể đổi được tổng tiền đó.
Trong minCoins_memo(amount, coins):
- Các base case vẫn giữ nguyên: amount == 0 trả về 0, amount < 0 trả về INT_MAX.
- Trước khi thực hiện vòng lặp tính toán, chúng ta kiểm tra if (memo_coins[amount] != INT_MAX). Nếu đúng, kết quả đã có, trả về ngay.
- Nếu chưa có, chúng ta lặp qua các loại đồng xu, gọi đệ quy cho phần còn lại amount - coin.
- Kết quả nhỏ nhất tìm được sau vòng lặp (tương ứng với việc thử tất cả các đồng xu có thể dùng đầu tiên) được lưu vào memo_coins[amount] trước khi hàm trả về.

Kỹ thuật Memoization biến độ phức tạp của bài toán Đổi tiền từ cấp số mũ (trong trường hợp xấu nhất) thành $O(\text{amount} \times |\text{coins}|)$ về thời gian (vì có amount + 1 trạng thái cần tính, mỗi trạng thái mất $O(|\text{coins}|)$ để lặp qua các đồng xu và thực hiện phép so sánh, cộng, và tra cứu memo). Độ phức tạp không gian là $O(\text{amount})$ cho memo_coins table và stack đệ quy.

Khi nào nên sử dụng Memoization?

Memoization là một lựa chọn tuyệt vời khi bạn gặp phải một giải thuật đệ quy có hai đặc điểm chính:

Cấu trúc con tối ưu (Optimal Substructure): Giải pháp tối ưu cho bài toán lớn có thể được xây dựng từ giải pháp tối ưu của các bài toán con. (Ví dụ: F(n) = F(n-1) + F(n-2), minCoins(amount) phụ thuộc vào minCoins(amount - coin)).
Bài toán con gối nhau (Overlapping Subproblems): Cùng một bài toán con được giải quyết nhiều lần trong quá trình thực hiện đệ quy "ngây thơ".

Nếu chỉ có cấu trúc con tối ưu mà không có bài toán con gối nhau (ví dụ: tìm đường đi ngắn nhất trong cây), đệ quy "ngây thơ" đã đủ hiệu quả (thường là đa thức), và Memoization sẽ không mang lại nhiều lợi ích về thời gian (chỉ thêm chi phí bộ nhớ và tra cứu), mặc dù nó vẫn đúng.

Memoization thường được xem là cách tiếp cận "từ trên xuống" (top-down) của Quy hoạch động (Dynamic Programming). Bạn bắt đầu từ bài toán lớn (top) và đệ quy xuống các bài toán con (down), sử dụng Memoization để "nhớ" kết quả và tránh tính toán lại. Ngược lại, Quy hoạch động "từ dưới lên" (bottom-up) sẽ xây dựng giải pháp bằng cách giải các bài toán con nhỏ nhất trước rồi dần dần kết hợp chúng lại để giải bài toán lớn hơn, thường sử dụng một mảng hoặc bảng (table) để lưu trữ kết quả (đây còn gọi là Tabulation).

Ưu và nhược điểm của Memoization

Ưu điểm:

Dễ dàng chuyển đổi từ đệ quy: Đối với một giải thuật đệ quy "ngây thơ", việc thêm Memoization thường chỉ yêu cầu thêm một cấu trúc lưu trữ và vài dòng kiểm tra/lưu trữ kết quả, giữ nguyên cấu trúc logic ban đầu của đệ quy.
Tính toán lười biếng (Lazy Evaluation): Chỉ những bài toán con thực sự cần thiết để giải bài toán ban đầu mới được tính toán. Nếu một bài toán con không nằm trên đường dẫn tính toán của bài toán lớn, nó sẽ không bao giờ được gọi và tính toán, không giống như phương pháp Tabulation (bottom-up) thường tính toán tất cả các trạng thái có thể.

Nhược điểm:

Chi phí không gian: Cần thêm không gian bộ nhớ để lưu trữ bảng ghi nhớ (memo table).
Chi phí gọi hàm đệ quy: Mỗi lời gọi đệ quy vẫn có một chút chi phí (quản lý stack). Với các bài toán có độ sâu đệ quy rất lớn, có thể gặp vấn đề tràn stack (stack overflow), mặc dù Memoization giúp giảm số lượng tổng cộng các lời gọi đệ quy so với bản ngây thơ.
Việc chọn và quản lý cấu trúc ghi nhớ: Phải chọn cấu trúc dữ liệu phù hợp (mảng, map, v.v.) và cơ chế đánh dấu "chưa tính" sao cho hiệu quả.

Bài tập ví dụ:

Ba mảng số

Trong một ngày làm việc bình thường, FullHouse Dev được một người thợ mộc tìm đến nhờ giải quyết một bài toán thú vị. Người thợ mộc đang cần tính toán số liệu cho một dự án đồ gỗ và gặp khó khăn với ba dãy số. FullHouse Dev quyết định giúp đỡ người thợ mộc giải quyết bài toán này.

Bài toán

Cho ba mảng số và hai số $M$ và $K$. Hãy tìm một bộ ba số $x, y, z$ có thứ tự từ điển nhỏ nhất sao cho có đúng $K$ chỉ số $i$ thỏa mãn $x \cdot A[i] + y \cdot B[i] + z \cdot C[i] = M$ với một số nguyên nào đó. Các giá trị $x$, $y$, và $z$ phải nằm trong các khoảng cho trước $[l_1, r_1]$, $[l_2, r_2]$, và $[l_3, r_3]$.

Một bộ ba số $(x_1, y_1, z_1)$ được coi là có thứ tự từ điển nhỏ hơn bộ ba số $(x_2, y_2, z_2)$ nếu tại vị trí đầu tiên mà hai bộ ba khác nhau, số trong bộ ba thứ nhất nhỏ hơn số tương ứng trong bộ ba thứ hai.

INPUT FORMAT:

Dòng đầu tiên chứa ba số nguyên $n$, $M$, $K$.
$n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $A[i]$, $B[i]$, $C[i]$.
Ba dòng cuối cùng, mỗi dòng chứa hai số nguyên $l_i$, $r_i$ thể hiện khoảng giá trị cho phép của $x$, $y$, $z$.

OUTPUT FORMAT:

Nếu không tồn tại đáp án, in ra -1.
Ngược lại, in ra ba số $x$, $y$, $z$ thỏa mãn yêu cầu.

Ví dụ

INPUT

OUTPUT

3 3 3

Giải thích

Với $K = 4$, điều kiện phải thỏa mãn tại tất cả các chỉ số. Ta có thể kiểm tra rằng bộ ba số $(3, 3, 3)$ thỏa mãn yêu cầu của bài toán. Hướng dẫn giải bài "Ba mảng số" bằng C++ (không code hoàn chỉnh):

Xác định không gian tìm kiếm: Bài toán yêu cầu tìm bộ ba số (x, y, z) trong các khoảng giá trị cho trước [l1, r1], [l2, r2], [l3, r3]. Đây là không gian tìm kiếm của chúng ta. Kích thước của không gian này là (r1 - l1 + 1) * (r2 - l2 + 1) * (r3 - l3 + 1).
Kiểm tra giới hạn: Quan sát giới hạn của các khoảng [l_i, r_i] (thường nhỏ, ví dụ: đến 10) và số lượng phần tử n (ví dụ: đến 100). Tích của các kích thước khoảng nhân với n (độ phức tạp của việc kiểm tra một bộ ba) là đủ nhỏ để thực hiện duyệt vét cạn (brute force).
Chiến lược tìm kiếm bộ ba nhỏ nhất từ điển: Để tìm bộ ba (x, y, z) có thứ tự từ điển nhỏ nhất, ta sẽ duyệt các giá trị theo thứ tự tăng dần: x trước, sau đó đến y, cuối cùng là z.
- Duyệt x từ l1 đến r1.
- Với mỗi giá trị x, duyệt y từ l2 đến r2.
- Với mỗi cặp (x, y), duyệt z từ l3 đến r3.
Kiểm tra điều kiện cho mỗi bộ ba (x, y, z): Đối với mỗi bộ ba (x, y, z) đang xét:
- Khởi tạo bộ đếm count bằng 0.
- Duyệt qua tất cả n chỉ số i (từ 0 đến n-1).
- Với mỗi chỉ số i, tính giá trị x * A[i] + y * B[i] + z * C[i].
- Nếu giá trị này bằng M, tăng bộ đếm count lên 1.
- Sau khi duyệt hết n chỉ số, kiểm tra xem count có bằng K hay không.
Xử lý kết quả:
- Nếu count == K, thì bộ ba (x, y, z) hiện tại là một đáp án thỏa mãn. Vì ta đang duyệt theo thứ tự từ điển tăng dần, bộ ba đầu tiên tìm được thỏa mãn điều kiện chính là bộ ba nhỏ nhất từ điển. In ra x, y, z và kết thúc chương trình.
- Nếu sau khi duyệt hết tất cả các bộ ba (x, y, z) trong không gian tìm kiếm mà không tìm thấy bộ ba nào thỏa mãn count == K, thì không tồn tại đáp án. In ra -1.

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

Comments

There are no comments at the moment.