AcWing 900. Integer partition

sample input :

5

sample output ：

7

You can think of the problem as Capacity is n The backpack , The volume of the objects in the backpack is 1 ~ n , Each item can be used unlimited times
It is equivalent to a Complete knapsack problem

It can be seen from the following figure ：

Further optimization is available ：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010, M = 1e9 + 7;

int n;
int f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % M;
            
    cout << f[n] << endl;
    
    return 0;
}

 

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010, M = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> n;
    f[0][0] = 1;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % M;
            
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % M;
    
    cout << res << endl;
    
    return 0;
}