Quy hoạch động trong c++

1. Quy hoạch động là gì?

Quy hoạch động (Dynamic Programming - DP) là phương pháp giải bài toán bằng cách chia bài toán lớn thành các bài toán nhỏ hơn, lưu kết quả của những bài toán nhỏ để sử dụng lại khi cần, giúp tránh tính toán lặp lại nhiều lần.

Ví dụ: Tính tổng các chữ số của số 1545.

Ta có:

1 + 5 + 4 + 5 = 15

Thông thường, chương trình phải tách từng chữ số để tính tổng. Nhưng nếu ta đã biết tổng chữ số của số 154 thì có thể tính tổng chữ số của số 1545 nhanh hơn.

Cụ thể:

tong(154) = 1 + 5 + 4 = 10

tong(1545) = tong(154) + 5
           = 10 + 5
           = 15

Đây chính là ý tưởng cơ bản của quy hoạch động: Sử dụng kết quả đã biết để tính kết quả mới.

2. Fibonacci nghĩa là gì

Dãy số Fibonacci được đặt theo tên của nhà toán học người Ý Leonardo Fibonacci,

Ta dùng bài toán Fibonacci đơn giản dưới đây

Ví dụ: Tính số Fibonacci thứ n
Ý tưởng: Muốn tính số Fibonacci thứ i, ta lấy hai số đứng trước cộng lại và lưu kết quả vào mảng.

#include <iostream>

using namespace std;

int main()

{

    int n = 10;

    int f[100];



    f[0] = 0;

    f[1] = 1;



    for (int i = 2; i <= n; i++)

    {

        f[i] = f[i - 1] + f[i - 2];

    }



    cout << f[n];



    return 0;

}

Giải thích từng bước

Khi n = 10, chương trình tính lần lượt:

Kết quả: f[10] = 55.

3. Hai đặc trưng cốt lõi

• Bài toán con chồng chéo: Các bài toán con xuất hiện lại nhiều lần trong quá trình tính toán.
• Cấu trúc con tối ưu: Lời giải tối ưu của bài toán lớn được xây dựng trực tiếp từ lời giải tối ưu của các bài toán con.

4. Các bước tiếp cận một bài toán quy hoạch động

1. Xác định trạng thái: Định nghĩa ý nghĩa của mảng/biến DP (ví dụ: dp[i] là kết quả với bài toán có kích thước i).
2. Tìm công thức truy hồi: Biểu diễn dp[i] thông qua các trạng thái nhỏ hơn đã được tính trước đó (ví dụ: dp[i] = dp[i-1] + dp[i-2]).
3. Xác định trường hợp cơ sở: Giá trị khởi tạo ban đầu cho các bài toán con nhỏ nhất (ví dụ: dp[0] = 0, dp[1] = 1).
4. Quyết định thứ tự tính toán: Chọn cách duyệt (từ dưới lên - Bottom-up hoặc từ trên xuống - Top-down kèm đệ quy có nhớ - Memoization).
5. Truy vết (nếu cần): Dùng bảng kết quả để phục hồi lại các bước đi tạo nên phương án tối ưu.

4. Hai phương pháp cài đặt chính

Cách 1: Top-down (Đệ quy có nhớ - Memoization)

Ý tưởng: Viết hàm đệ quy tự nhiên, lưu lại kết quả của các bài toán con đã tính vào một mảng/bảng để không phải tính lại.

Ví dụ tính số Fibonacci trong C++:

#include <iostream>

#include <vector>

using namespace std;

long long memo[100];
long long fib(int n) {

    if (n <= 1) return n;

    if (memo[n] != -1) return memo[n]; // Nếu đã tính thì trả về luôn

    return memo[n] = fib(n - 1) + fib(n - 2);

}
int main() {

    int n = 10;

    fill_n(memo, 100, -1);

    cout << "Fibonacci(" << n << ") = " << fib(n);

    return 0;

}

Cách 2: Bottom-up (Lập bảng - Tabulation)

Ý tưởng: Khởi tạo từ các trường hợp cơ sở nhỏ nhất, dùng vòng lặp để xây dựng dần lên đến bài toán lớn.

#include <iostream>

#include <vector>

using namespace std;



int main() {

    int n = 10;

    vector<long long> dp(n + 1);

    dp[0] = 0;

    dp[1] = 1;



    for (int i = 2; i <= n; i++) {

        dp[i] = dp[i - 1] + dp[i - 2]; // Công thức truy hồi

    }



    cout << "Fibonacci(" << n << ") = " << dp[n];

    return 0;

}

5. Xây dựng công thức quy hoạch động

Muốn tính tổng chữ số của một số nguyên dương n, ta có thể tách n thành hai phần:

• n / 10: Phần số còn lại sau khi bỏ chữ số cuối.
• n % 10: Chữ số cuối cùng của n.

Ví dụ, với n = 1545:

1545 / 10 = 154
1545 % 10 = 5

Do đó:

tong(1545) = tong(154) + 5

Tổng quát, ta có công thức:

tong[n] = tong[n / 10] + n % 10

Trong đó:

• tong[n]: Tổng các chữ số của số n.
• tong[n / 10]: Tổng các chữ số của số sau khi bỏ chữ số cuối.
• n % 10: Chữ số cuối cùng của n.

6. Trạng thái cơ sở

Trước khi tính các số lớn hơn, ta cần biết kết quả của số nhỏ nhất.

Số 0 không có chữ số nào khác 0, vì vậy tổng chữ số của số 0 bằng 0.

tong[0] = 0;

Đây là trạng thái cơ sở để chương trình tính các trạng thái tiếp theo.

7. Tính kết quả từ nhỏ đến lớn

Ta sử dụng vòng lặp để tính tổng chữ số của các số từ 1 đến MAXN.

for (int i = 1; i <= MAXN; i++)

{

    tong[i] = tong[i / 10] + i % 10;

}

Ví dụ với các số từ 0 đến 15:

Ví dụ: Khi tính tong[15], chương trình đã có tong[1] = 1 nên:

tong[15] = tong[1] + 5 = 6

Điều quan trọng là khi tính tong[i], giá trị tong[i / 10] đã được tính trước đó.

8. Chương trình C++ hoàn chỉnh

#include <iostream>

using namespace std;

const int MAXN = 1000000;

int tong[MAXN + 1];
void khoiTao()

{

    for (int i = 1; i <= MAXN; i++)

    {

        tong[i] = tong[i / 10] + i % 10;

    }

}
int tongchuso(int n)

{

    if (n < 0 || n > MAXN)

        return -1;
    return tong[n];

}
int main()

{

    khoiTao();
    cout << tongchuso(1545) << endl;

    cout << tongchuso(12345) << endl;

    cout << tongchuso(6789) << endl;
    return 0;

}

Kết quả:

15
15
30

9. Vì sao cách này nhanh?

Nếu không sử dụng quy hoạch động, mỗi lần tính tổng chữ số, chương trình phải dùng vòng lặp để tách từng chữ số.

Ví dụ, muốn tính tổng chữ số của 1545, chương trình phải thực hiện các phép chia và lấy phần dư nhiều lần.

Với quy hoạch động, chương trình tính trước kết quả cho tất cả các số từ 0 đến MAXN.

Sau đó, khi cần tính tổng chữ số của 1545, chỉ cần lấy:

return tong[1545];

Lưu ý: Quy hoạch động không phải lúc nào cũng nhanh hơn. Nếu chỉ tính tổng chữ số của một vài số, tính trực tiếp thường phù hợp hơn vì không cần khởi tạo cả mảng. Quy hoạch động có lợi khi cần tra cứu nhiều lần trong một phạm vi đã xác định.

10. Quy trình xây dựng thuật toán quy hoạch động

1. Xác định trạng thái: tong[n] là tổng chữ số của số n.
2. Xác định trạng thái cơ sở: tong[0] = 0.
3. Tìm công thức chuyển: tong[n] = tong[n / 10] + n % 10.
4. Chọn thứ tự tính: Tính từ số nhỏ đến số lớn.
5. Lưu kết quả: Ghi kết quả vào mảng tong.
6. Sử dụng lại: Khi cần kết quả, lấy trực tiếp từ mảng.

11. Bài tập vận dụng

Bài 1: Dựa vào công thức quy hoạch động, hãy tính tổng chữ số của các số 123, 4567 và 9999.

Bài 2: Thay MAXN bằng 100000. Hãy tính tổng chữ số của số 98765.

Bài 3: Viết chương trình tính tổng chữ số của nhiều số nhập từ bàn phím bằng cách sử dụng mảng quy hoạch động.

Trạng thái cơ sở → Công thức chuyển → Thứ tự tính → Lưu kết quả → Sử dụng lại.