Bài toán cụ thể

Có bao nhiêu nghiệm ~(x_1, x_2, x_3, x_4, x_5)~ nguyên dương thỏa mãn:

• ~x_1 ≤ x_2 ≤ x_3 ≤ x_4 ≤ x_5~
• ~x_1 + x_2 + x_3 + x_4 + x_5 = 8~

~3~ nghiệm thỏa mãn:

• ~1 + 1 + 1 + 1 + 4 = 8~

• ~1 + 1 + 1 + 2 + 3 = 8~

• ~1 + 1 + 2 + 2 + 2 = 8~

Hướng giải quyết

• Gọi ~dp[i][j]~ là số cách tạo thành tổng ~j~ dùng đến đúng ~i~ số nguyên dương.

Cơ sở quy hoạch động

• ~dp[i][i] = 1~ với mọi ~i~ từ ~1~ đến ~k~ Biểu thị cho việc luôn tìm ra cách phân tích số có tổng ~i~ bằng việc dùng đúng ~i~ số nguyên dương.

Chả hạn:

• ~3 = 1 + 1 + 1~

• ~5 = 1 + 1 + 1 + 1 + 1~

Tìm nguyên tắc duyệt

• Xác định rằng không thể tạo thành tổng ~x~ mà lại dùng nhiều hơn ~x~ số nguyên dương.

Chả hạn: Không thể tạo thành tổng ~7~ mà dùng đúng ~8~ số nguyên dương

• Do đó chỉ xét các trường hợp tạo thành tổng ~i, i+1, i+2,…~ đến ~n~ dùng đúng ~i~ số nguyên dương. Quá trình xét này thể hiện qua vòng for:

for (int i = 1; i <= k; i++){
    for (int j = i; j <= n; j++){
        //dp
    }
}

Tìm hệ thức truy hồi

• Để tạo thành tổng ~j~ dùng đúng ~i~ số nguyên dương, ta có các trường hợp sau:

Trường hợp 1: Số đầu tiên trong dãy số hạng là số ~1~.

• Khi đó số cách thỏa mãn trường hợp ~1~ chính là là cách tạo thành tổng ~j-1~, dùng đúng ~i-1~ số hạng.
• Tức là ta thêm một số hạng duy nhất là số ~1~, trong đó số hạng này nằm ở đầu dãy.

=> Chỉ có một cách duy nhất để dùng thêm đúng ~1~ số như vậy, tức là không thể đặt số ~1~ này vào ví trí nào khác ngoài vị trí đầu tiên

Chả hạn: có đúng ~3~ cách để tạo thành số ~7~ dùng đúng ~2~ số nguyên dương:

• ~1 + 6 = 7~

• ~2 + 5 = 7~

• ~3 + 4 = 7~

Thì cũng chỉ có ~3~ cách để thêm được số ~1~ vào trong bộ đáp án này, tạo thành tổng ~8~ dùng đúng ~3~ số nguyên dương:

• ~1 + 1 + 6 = 8~

• ~1 + 2 + 5 = 8~

• ~1 + 3 + 4 = 8~

Do đó ~F_1 = dp[i-1][j-1]~, trong đó ~F_1~ là số cách thỏa mãn trường hợp ~1~

Trường hợp 2: Số hạng đầu tiên trong dãy không phải là ~1~, bắt đầu là các số ~≥ 2~

• Ở trên ra có ~3~ cách tạo thành tổng bằng ~8~ dùng đúng ~3~ số nguyên dương, trong đó các số đầu tiên bằng ~1~

• Giờ ta sẽ thử xem có bao nhiêu cách tạo thành tổng bằng ~8~ dùng đúng ~3~ số nguyên dương, trong đó số đầu tiên khác ~1~

Ví dụ: Ngoài ~3~ cách

• ~1 + 1 + 6 = 8~

• ~1 + 2 + 5 = 8~

• ~1 + 3 + 4 = 8~

Thì còn có thêm hai cách nữa:

• ~2 + 2 + 4 = 8~

• ~2 + 3 + 3 = 8~

Cấu hình của ~2~ cách này tương đương với cấu hình của ~2~ cách tạo thành tổng bằng ~5~ dùng ~3~ số nguyên dương, chỉ khác là các số hạng đều cộng thêm ~1~ đơn vị:

• ~1 + 1 + 3 = 5~

• ~1 + 2 + 2 = 5~

Số cách thỏa mãn điều kiện này chính là ~dp[i][j-i]~ (do mỗi số hạng đều bị cộng thêm ~1~ đơn vị tối thiểu)

• Đây là nghệ thuật của quy hoạch động, không phải lúc nào cũng có bài vở để nhìn ra được!

Do đó ~F_2 = dp[i][j-i]~, trong đó ~F_2~ là số cách thỏa mãn trường hợp ~2~

Kết luận

🔍 Trường hợp 1 và Trường hợp 2 cho ra hai loại nghiệm không bị đếm trùng nhau và cùng thỏa mãn việc dùng đúng ~i~ số nguyên dương tạo thành tổng ~j~

Do đó kết hợp trực tiếp nghiệm của hai trường hợp sẽ cho ra kết quả:

~dp[i][j] = F_1 + F_2 = dp[i-1][j-1] + dp[i][j-i]~

Code

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

const int maxn = 1e3 + 10;
int x[maxn];
int n,k;

void Print(){
    for (int i = 1; i <= k; i++) cout << x[i] << " ";
    cout << "\n";
}

void Try(int pos, int sum){
    if (pos > k){
        Print();
        return;
    }

    if (pos == k){
        if (n - sum < x[pos-1]) return;
        x[pos] = n-sum;
        Print();
        return;
    }

    for (int i = x[pos-1]; i <= n-sum; i++){
       x[pos] = i;
       Try(pos+1, sum+i);
   }
}

int dp[maxn][maxn];
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   cin >> n >> k;

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

   cout << dp[k][n];

   cout << "\n";

   x[0] = 1;
   Try(1, 0);
}