Hiểu bài toán

Cho hai số nguyên dương $M$ và $K$. Đếm số cách biểu diễn $M$ dưới dạng tổng của các số Fibonacci (không phân biệt thứ tự các số hạng trong tổng) sao cho số lượng các số Fibonacci giống nhau (bằng nhau) trong tổng không vượt quá $K$. Gọi các số Fibonacci là $F1=1, F2=1, F3=2, F4=3, \dots$. Ví dụ, với $M=4, K=1$, các cách biểu diễn hợp lệ là $3+1$ (hai số Fibonacci khác nhau, số lượng mỗi loại là 1, đều $\le 1$? Không, bài này có vẻ hiểu nhầm. Đọc kỹ Solution 2: if (n >= f[pos]) soCach(pos, n - f[pos], same + 1); soCach(pos + 1, n, 0);. Solution 1: dp[i][s] = dp[i-1][s] (không dùng $f[i]$) và cộng dồn các trường hợp dùng $t$ số $f[i]$. Solution 3: dp[s] += dp[s - t*f[i]].

Phân tích bài toán:

• Solution 1, 3 dùng quy hoạch động.
• Solution 2 dùng đệ quy quay lui (Backtracking) với kiểm soát số lượng.

Theo code, bài toán yêu cầu: Cho $M, K$. Tìm số cách chọn các số Fibonacci (có thể lặp lại) để tổng bằng $M$, với điều kiện ràng buộc: Số lần xuất hiện của mỗi số Fibonacci trong tổng không được vượt quá $K$.

Ví dụ: $M=4, K=1$. Các số Fibonacci $\le 4$: $1, 2, 3$. Các cách:

1. $3 + 1$ (dùng $F4=3, F1=1$). Số lượng mỗi loại là 1. Nếu $K=1$, hợp lệ.
2. $2 + 2$ (dùng $F3=2$). Số lượng $F3$ là 2. Nếu $K \ge 2$ thì hợp lệ. Nếu $K=1$, không hợp lệ.
3. $2 + 1 + 1$ (dùng $F3=2, F1=1$). Số lượng $F_1$ là 2. Nếu $K=1$, không hợp lệ.

Như vậy bài toán là: Đếm số cách viết $M$ dưới dạng tổng các số Fibonacci $fi$ sao cho số lượng mỗi $fi$ trong tổng $\le K$. Các số Fibonacci được dùng là $1, 2, 3, 5, \dots$ (bỏ qua $F_2=1$ để tránh lặp).

Lưu ý: Solution 1 dùng f[0]=f[1]=1 và f[i] = f[i-1] + f[i-2] với $i=2..11$. Mảng dp[12][101] chỉ chứa $M$ lên tới 100? Không, s chạy tới m nhưng dp khai báo [12][101]. Nếu m lớn, tràn mảng. Có lẽ m nhỏ. Solution 2 dùng f[105] và n, k (có thể đổi tên biến). Solution 3 dùng dp[105] và f[20].

Giả sử đề bài thpttd_47 có $M \le 100$ và $K$ nhỏ (ví dụ $K \le 10$).

Đề bài gốc (nếu có) có thể yêu cầu: Đếm số cách biểu diễn $M$ thành tổng các số Fibonacci sao cho không có số Fibonacci nào xuất hiện quá $K$ lần.

Các cách tiếp cận

Cách Quay lui (Backtracking) - Solution 2

void fibo() {
    f[1] = 1, f[2] = 2;
    FOR(i, 3, 99) f[i] = f[i - 1] + f[i - 2];
}

void soCach(int pos, int n, int same) {
    if (n < 0 || same > k || pos > 100) return;
    if (n == 0) {
        res++;
        return;
    }
    // Thêm số Fibonacci f[pos] vào tổng
    if (n >= f[pos]) soCach(pos, n - f[pos], same + 1);
    // Bỏ qua số Fibonacci f[pos], chuyển sang số tiếp theo
    soCach(pos + 1, n, 0);
}

• Time Complexity: O(Phức tạp)
• Space Complexity: O(1)

Đây là phương pháp DFS/Quay lui thuần túy. Hàm soCach(pos, n, same) cố gắng tạo tổng n bằng cách sử dụng các số Fibonacci từ chỉ số pos trở đi.

• pos: Chỉ số của số Fibonacci đang xét.
• n: Giá trị còn lại cần tạo.
• same: Số lượng số Fibonacci f[pos] đã sử dụng liên tiếp (hoặc cùng loại).

Logic:

1. Nếu n giảm về 0, tìm được một cách biểu diễn hợp lệ, tăng biến đếm res.
2. Nếu n < 0, same > k, hoặc pos quá lớn thì dừng.
3. Gọi đệ quy 1: Chọn f[pos]. Giảm n đi f[pos], tăng same lên 1. Ta tiếp tục dùng f[pos] (vì pos không đổi).
4. Gọi đệ quy 2: Không chọn f[pos] nữa. Giữ nguyên n, chuyển sang f[pos+1], reset same về 0.

Phương pháp này chậm vì số lượng trường hợp có thể rất lớn nếu $M$ lớn, nhưng với $M$ nhỏ thì có thể chấp nhận được.

Cách Quy hoạch động - Solution 3

dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int s = m; s >= 0; s--) {
        for (int t = 1; t <= k; t++) {
            if (s >= t * f[i]) 
                dp[s] += dp[s - t * f[i]];
        }
    }
}
cout << dp[m];

• Time Complexity: O(N * M * K)
• Space Complexity: O(M)

Đây là cách tiếp cận DP dạng 'Balo giới hạn số lượng' (Bounded Knapsack).

• dp[s]: Số cách tạo ra tổng s.
• f[i]: Danh sách các số Fibonacci.
• k: Số lượng tối đa của mỗi loại số Fibonacci.

Cách hoạt động: Ta duyệt qua từng số Fibonacci f[i]. Với mỗi giá trị s đang xét, ta thử thêm vào t số f[i] (từ 1 đến k). Công thức: dp[s] += dp[s - t * f[i]].

Vấn đề của code này:

• Vòng lặp s chạy từ 0 đến m. Nếu s chạy từ 0 đến m và dùng dp[s - ...], ta có thể cộng dồn nhiều lần cùng một số Fibonacci trong một lượt duyệt (vấn đề 'Balo vô hạn'). Ví dụ: dp[3] có thể được tính từ dp[1] (dùng 1 số f[i]). Sau đó khi xét s=5, dp[5] tính từ dp[3] (dùng thêm 1 số f[i]), vô tình dùng f[i] hai lần. Tuy nhiên, vòng lặp t đã xử lý việc dùng t lần cùng lúc, nhưng nếu vòng lặp s chạy 0 -> m thì dp[s] mới tính được dùng lại dp[s] cũ (vừa update).

Để tránh dùng quá số lượng hoặc dùng lặp lại sai cách, ta thường dùng 2 mảng hoặc chạy s ngược. Code này s chạy m -> 0 là đúng để tránh dùng lại chính f[i] nhiều lần không kiểm soát, nhưng với t chạy 1->k, nó cộng dồn dp[s] += dp[s - t*f[i]].

Ví dụ: f[i]=2, k=2.

• s=4: dp[4] += dp[2] (dùng 1 số) và dp[4] += dp[0] (dùng 2 số). Nếu s chạy 0 -> m: Khi xét s=4, dp[2] chưa được update cho f[i] này. Khi xét s=2, dp[2] update từ dp[0]. Khi quay lại s=4 (nếu có), dp[2] đã update.

Tuy nhiên, code s chạy m -> 0 là để đảm bảo dp[s - t*f[i]] là giá trị cũ (chưa dùng f[i]).

Độ phức tạp: O(N * M * K). Với M=100, N~20, K=10, khoảng 20k thao tác.

Cách Quy hoạch động - Solution 1

for(int i = 0; i < 12; i++) dp[i][0] = 1;
for(int i = 1; i < 12; i++) {
    for(int s = 0; s <= m; s++) {
        dp[i][s] = dp[i-1][s]; // Không dùng số Fibonacci thứ i
        for(int t = 1; t <= k; t++) {
            ll val = s - (f[i] * t);
            if(val >= 0) {
                dp[i][s] += dp[i-1][val]; // Dùng t số Fibonacci thứ i
            }
        }
    }
}
cout << dp[11][m];

• Time Complexity: O(N * M * K)
• Space Complexity: O(N * M)

Đây là quy hoạch động 2 chiều.

• dp[i][s]: Số cách tạo tổng s bằng cách sử dụng các số Fibonacci từ chỉ số 1 đến i.

Logic:

• dp[i][s] = dp[i-1][s]: Không dùng số Fibonacci f[i].
• dp[i][s] += dp[i-1][s - t*f[i]]: Dùng t số Fibonacci f[i].

Phương pháp này rõ ràng, dễ hiểu. Nó bao quát hết các trường hợp.

• i chạy từ 1 đến 11 (thay vì 100 như Solution 2). Điều này cho thấy m rất nhỏ (mặc dù dp khai báo [12][101]). Nếu m lớn hơn 100, code này sẽ lỗi.

So sánh với Solution 3:

• Solution 3 dùng 1 mảng dp, tối ưu không gian.
• Solution 1 dùng 2 mảng (truy suất i-1), rõ ràng hơn nhưng tốn bộ nhớ hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là biến thể của bài toán 'Balo' (Knapsack) với giới hạn số lượng (Bounded Knapsack). Số Fibonacci đóng vai trò là các item có trọng số và giá trị bằng nhau.
• Số Fibonacci chỉ cần xét từ 1 đến số nhỏ hơn hoặc bằng M. Số lượng số Fibonacci này rất nhỏ (khoảng $\log_{\phi} M$).
• Nếu M nhỏ (ví dụ $M \le 100$), các giải pháp DP đều chạy rất nhanh. Nếu M lớn, cần tối ưu hơn (ví dụ quy hoạch động trên các số Fibonacci, nhưng ở đây M có vẻ nhỏ).

Lỗi thường gặp

• Lặp số Fibonacci: Phải đảm bảo rằng khi dùng DP, ta không đếm trùng các cách do thứ tự các số Fibonacci gây ra. Solution 1 và 3 đều xử lý đúng bằng cách duyệt qua từng loại Fibonacci và cộng dồn vào kết quả.
• Quên số Fibonacci 1 hoặc 2: Chuỗi Fibonacci thường bắt đầu bằng 1, 1 hoặc 1, 2. Solution 1 dùng f[0]=f[1]=1 (F1, F2) và lặp 12 phần tử. Solution 2 bắt đầu bằng f[1]=1, f[2]=2. Solution 3 bắt đầu f[0]=1, f[1]=2. Cần thống nhất danh sách các số Fibonacci được phép dùng (thường bỏ qua số 1 thứ hai để tránh trùng lặp nếu không có ràng buộc về mặt vị trí).
• Tràn mảng: Solution 1 khai báo dp[12][101] nhưng vòng lặp s chạy đến m. Nếu m > 100, lỗi tràn mảng. Solution 3 khai báo dp[105] và f[20].
• Logic đệ quy Solution 2: Biến same dùng để đếm số lượng số Fibonacci cùng loại đang được dùng. Nếu same > k thì dừng. Đây là cách kiểm soát số lượng trực tiếp trong đệ quy.