partition2 - LQDOJ

// Comeback cực mạnh
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5, mod = 1e9 + 7;
int n, dp[350][N+1];
void read()
{
    cin >> n;
    dp[0][0] = 1;
}
/* dp i j : số nghiệm a1 + a2 + ... + ai == j
TH1 : ai = 1
số nghiệm : dp i - 1 j - 2 * i + 1
TH2 : ai = 2
số nghiệm : dp i j - i */
void solve()
{
    for (int i = 1; i * i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            if (j >= i)
            {
                dp[i][j] += dp[i][j - i];
            }
            if (j >= 2 * i - 1)
            {
                dp[i][j] += dp[i - 1][j - 2 * i + 1];
            }
            dp[i][j] = dp[i][j] % mod;
        }
    }
    int sum = 0;
    for (int i = 1; i * i <= n; ++ i)
    {
        sum += dp[i][n];
        sum = sum % mod;
    }
    cout << sum;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
}