Hiểu bài toán

Bài toán yêu cầu tính số cách để một con ếch nhảy từ vị trí 0 đến vị trí N trên một đường thẳng. Con ếch có k bước nhảy khác nhau với độ dài b1, b2, ..., b_k. Với mỗi bước nhảy, con ếch có thể chọn bất kỳ độ dài nào trong số k độ dài cho phép. Chúng ta cần đếm tất cả các chuỗi bước nhảy (với thứ tự có thể lặp lại) sao cho tổng độ dài bằng N.

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

Cách Quy hoạch động cơ bản

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> b(k);
    for (int i = 0; i < k; i++) {
        cin >> b[i];
    }

    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // Base case: 1 cách để ở vị trí 0

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            if (i - b[j] >= 0) {
                dp[i] += dp[i - b[j]];
            }
        }
    }

    cout << dp[n] << endl;
    return 0;
}

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

Đây là cách tiếp cận quy hoạch động chuẩn. Ta định nghĩa dp[i] là số cách để đến được vị trí i.

• Base case: dp[0] = 1 (có 1 cách duy nhất là không nhảy).
• Công thức truy hồi: dp[i] = sum(dp[i - b[j]]) với mọi j sao cho i >= b[j].
• Nghĩa là để đến vị trí i, con ếch có thể nhảy từ vị trí i - b[j] với mỗi độ dài b[j].
• Ta duyệt i từ 1 đến N, và với mỗi i, duyệt qua tất cả các bước nhảy có thể.

Ví dụ với N=8, b=[2,3]:

• dp[0] = 1
• dp[1] = 0 (không thể đến vị trí 1)
• dp[2] = dp[0] = 1
• dp[3] = dp[0] + dp[1] = 1 + 0 = 1
• dp[4] = dp[2] + dp[1] = 1 + 0 = 1
• dp[5] = dp[3] + dp[2] = 1 + 1 = 2
• dp[6] = dp[4] + dp[3] = 1 + 1 = 2
• dp[7] = dp[5] + dp[4] = 2 + 1 = 3
• dp[8] = dp[6] + dp[5] = 2 + 2 = 4

Kết quả là 4, đúng như mong đợi.

Cách Đệ quy có nhớ (Memoization)

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> b;
vector<long long> memo;

long long solve(int pos) {
    if (pos == 0) return 1;
    if (pos < 0) return 0;

    if (memo[pos] != -1) return memo[pos];

    long long ways = 0;
    for (int i = 0; i < k; i++) {
        if (pos >= b[i]) {
            ways += solve(pos - b[i]);
        }
    }

    return memo[pos] = ways;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    b.resize(k);
    for (int i = 0; i < k; i++) {
        cin >> b[i];
    }

    memo.assign(n + 1, -1);

    cout << solve(n) << endl;
    return 0;
}

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

Cách tiếp cận này sử dụng đệ quy kết hợp với memoization (lưu trữ kết quả đã tính).

• Hàm solve(pos) trả về số cách để đến vị trí pos.
• Base cases: pos == 0 trả về 1, pos < 0 trả về 0.
• Nếu pos đã được tính trước đó, trả về giá trị đã lưu.
• Nếu chưa, tính đệ quy: duyệt qua tất cả các bước nhảy có thể, gọi solve(pos - b[i]) và cộng dồn.
• Lưu kết quả vào mảng memo trước khi trả về.

Cách này về mặt lý thuyết có cùng độ phức tạp với cách 1, nhưng thường dễ hiểu hơn đối với người mới học quy hoạch động. Tuy nhiên, nó có thể gây tràn stack với N lớn (dù N=50 ở đây không phải vấn đề).

Cách Quy hoạch động tối ưu (mảng 1 chiều)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n, k;
    cin >> n >> k;
    vector<long long> dp(n + 1, 0);

    // Đọc các bước nhảy
    vector<long long> jumps(k);
    for (int i = 0; i < k; i++) {
        cin >> jumps[i];
    }

    dp[0] = 1;

    // Duyệt qua từng vị trí
    for (int i = 1; i <= n; i++) {
        // Với mỗi vị trí, thử tất cả các bước nhảy
        for (int j = 0; j < k; j++) {
            if (i >= jumps[j]) {
                dp[i] += dp[i - jumps[j]];
            }
        }
    }

    cout << dp[n] << endl;
    return 0;
}

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

Đây là phiên bản tối ưu và phổ biến nhất của thuật toán quy hoạch động cho bài toán này.

Ưu điểm:

1. Dễ cài đặt và hiệu quả
2. Không sử dụng đệ quy, tránh nguy cơ tràn stack
3. Dễ dàng Debug

Cách hoạt động:

• Mảng dp[n+1] lưu số cách đến mỗi vị trí
• dp[0] = 1 là trường hợp cơ sở
• Với mỗi i từ 1 đến n, dp[i] được tính bằng tổng dp[i - b] với mọi b trong danh sách bước nhảy

Độ phức tạp:

• Thời gian: O(N*K) - với N=50, K=10, chỉ cần 500 phép tính
• Không gian: O(N) - mảng dp có 51 phần tử

Đây là giải pháp tối ưu cho ràng buộc của bài toán.

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

Bài học kinh nghiệm

• Bài toán có thể coi là bài toán 'tổng các số' (coin sum) với order quan trọng - đây là biến thể 'coin change' với thứ tự có ý nghĩa
• Quy hoạch động là cách tiếp cận tối ưu với độ phức tạp O(N*K), hoàn toàn chấp nhận được với N≤50, K≤10
• Cần khởi tạo dp[0] = 1 vì có 1 cách duy nhất để ở vị trí xuất phát (không nhảy)

Lỗi thường gặp

• Quên khởi tạo dp[0] = 1, dẫn đến kết quả sai là 0
• Sử dụng biến sai kiểu (int thay cho long long) có thể gây tràn số, nhưng với N=50 thì int vẫn đủ
• Bỏ qua kiểm tra điều kiện i >= b[j] khi truy cập dp[i - b[j]] có thể gây truy cập ngoài vùng nhớ
• Đặt sai giới hạn vòng lặp (ví dụ: i <= n+1 thay vì i <= n) có thể gây lỗi