# Lời giải bài IPARB
> Tác giả `Lam`

## Đề

Cho số nguyên dương $n$, mỗi dãy số nguyên dương không giảm có tổng bằng $n$ được gọi là một cách phân tích số $n$.

**Yêu cầu:** Đếm số cách phân tích số $n$ $( n <= 400 )$

## Thuật toán ngây thơ

Làm giống bài IPARA và in ra số cách phân tích.

[**Lời giải bài IPARA**](https://hackmd.io/@M30/B10LUutQo)

## Thuật toán full
Ta sẽ dùng phương pháp quy hoạch động cho bài này.

Gọi `dp(sum,last)` là số cách phân tích số `sum` sao cho số cuối cùng là `last`
Gọi `next` là giá trị tiếp theo ta muốn gắn vào `(next>=last)`, ta có công thức quy hoạch động như sau:

    for (int next = last; next <= n; next++) 
        dp[sum+next][next] += dp[sum][last];

### Giải thích
Ta muốn thêm giá trị `next` vào sau cách phân tích hiện tại
=> Tổng giả trị phân tích của ta sẽ trở thành `sum+next`
=> Công thức: `dp(sum+next,next) = dp(sum,last)`

### Code

    for (int next = 1; next <= n; next++) dp[next][next]++;
    for (int sum = 1; sum <= n; sum++)
        for (int last = 1; last <= sum; last++)
            for (int next = last; next <= n; next++)
                dp[sum+next][next] += dp[sum][last];
    int ans = 0;
    for (int last=1; last<=n; last++) ans += dp[n][last];
    cout << ans;

### Nhận xét

Độ phức tạp: $O(n^3)$
Không gian: $O(n^2)$

## Thuật toán full v2
Ta sẽ áp dụng phương pháp quy hoạch động cho bài này.

Gọi `dp(sum,val)` là số cách phân tích số `sum` sao cho số cuối cùng có giá trị bé hơn hoặc bằng`val`.

Ta có công thức quy hoạch động như sau:

    dp[sum][val] = dp[sum][val-1] + dp[sum-val][val];

### Giải thích

**Trường hợp 1 (giá trị cuối cùng < `val` )**
Số cách phân tích là `dp(sum,val-1)`

**Trường hợp 2 (giá trị cuối cùng = `val` )**
Gọi `last` là giá trị trước đó của cách phân tích ta đang xét => `last <= val`
Vậy, số cách phân tích `sum` mà có giá trị cuối cùng là `val`
= số cách phân tích `sum-val` mà có giá trị cuối cùng là `last <= val`
= `dp(sum-val,val)`

> Suy ra: `dp(sum,val) = dp(sum,val-1) + dp(sum-val,val)`

### Code

    
    for (int last = 0; last <= n; last++) dp[0][last] = 1;
    for (int sum = 1; sum <= n; sum++)
        for (int last = 1; last <= sum; last++)
            dp[sum][last] = dp[sum][last-1] + dp[sum-last][last];
            
    int ans = dp[n][n];
    cout << ans;

### Nhận xét

Độ phức tạp: $O(n^2)$
Không gian: $O(n^2)$

### Code tối ưu không gian

    
    dp[0] = 1;
    for (int last = 1; last <= n; last++)
        for (int sum = last; sum <= n; sum++)
            dp[sum] += dp[sum-last];
    int ans = dp[n];
    cout << ans;

### Nhận xét

Độ phức tạp: $O(n^2)$
Không gian: $O(n)$

## Thuật toán full v3
Ta có thể show trình implementation của mình bằng cách cho template bignum vào và thể hiện rằng mình rất pro :33.
[Tìm hiểu về template bigint cho C++ (bản tiếng Anh)](https://codeforces.com/blog/entry/16380)

### Code

#include <bits/stdc++.h>
#define taskname "iparb"
using namespace std;

const int maxn = 410;
const int mod = 10;
int n;

struct bignum
{
    int m[20];
};

bignum dp[maxn];

bignum operator+ (bignum a, bignum b)
{
    bignum c;
    c.m[0] = max(a.m[0],b.m[0]);
    int nho = 0;
    for (int i = 1; i <= c.m[0]; i++)
    {
        if (i > a.m[0]) a.m[i] = 0;
        if (i > b.m[0]) b.m[i] = 0;
        c.m[i] = ( a.m[i] + b.m[i] + nho ) % mod;
        nho = ( a.m[i] + b.m[i] + nho ) / mod;
    }
    if (nho > 0)
    {
        c.m[0]++;
        c.m[c.m[0]] = nho;
    }
    return c;
}

void print(bignum a)
{
    for (int i = a.m[0]; i >= 1; i--)
    {
        cout << a.m[i];
    }
    cout << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    freopen(taskname".inp","r",stdin);
    freopen(taskname".out","w",stdout);
    cin >> n;
    for (int i = 1; i <=n ; i++) dp[i].m[0] = 1, dp[i].m[1] = 0;
    dp[0].m[0] = dp[0].m[1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            dp[j] = dp[j] + dp[j-i];
    print(dp[n]);
}

### Nhận xét

Độ phức tạp: $O(n^2*20)$
Không gian: $O(n*20)$