Question

Bài 2: Phân tích số
Cho số tự nhiên n (n ≤ 400). Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.
Ví dụ: Với n=5, có 7 cách phân tích:
1. 5 = 1 + 1 + 1 + 1 + 1
2. 5 = 1 + 1 + 1 + 2
3. 5 = 1 + 1 + 3
4. 5 = 1 + 2 + 2
5. 5 = 1 + 4
6. 5 = 2 + 3
7. 5 = 5

yêu cầu không dùng đệ quy

Answer 1

Bạn sài Quy hoạch động đi

c++:

#include <iostream>
#include <vector>

using namespace std;

const int N = (int) 1e5 + 5;
const int MOD = (int) 1e9;

int a[N];
int n;

int main() {
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> p;
    for (int i = 1;;) {
        p.push_back(i * (3 * i - 1) / 2);
        if (p.back() >= n) break;
        i = -i;
        if (i > 0) i++;
    }

    a[0] = 1;
    for (int i = 1; i <= n; ++i) {
        int sign = 1, cnt = 0;
        for (int j : p) {
            if (j > i) break;
            a[i] += sign * a[i - j];
            if (a[i] < 0) a[i] += MOD;
            if (a[i] >= MOD) a[i] -= MOD;
            cnt += 1;
            if (cnt == 2) {
                cnt = 0;
                sign = -sign;
            }
        }
    }

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