Dynamic programming [4] (counting class DP) example: integer partition

Example ： Integer partition

link ：900. Integer partition - AcWing Question bank

A positive integer  nn  It can be expressed as the sum of several positive integers , Form like ：n=n1+n2+…+nkn=n1+n2+…+nk, among  n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1.

We call such a representation a positive integer  n  A division of .

Now let's give a positive integer  n, Please find out  n  How many different division methods are there .

Input format

All in one line , Contains an integer  n.

Output format

All in one line , Contains an integer , Indicates the total number of partitions .

Because the answer can be big , Please correct the output result  1e9+7  modulus .

Data range

1≤n≤10001≤n≤1000

sample input :

5

sample output ：

7

Ideas ： It can be interpreted as a complete backpack , Yes n Items , The values are 1,2,3…n, The volume is also 1,2,3…n, Now the capacity of the backpack is n, Ask the number of schemes that just fill the backpack （ Note that each item can have countless ）.

 

So the state transfer equation is ：

    f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2*i]+....f[i-1][j-i*s]

    Optimize it ：

    f[i][j-i]=          f[i-1][j-i]+f[i-1][j-2*i]+....f[i-1][j-i*s]

Note that there is nothing missing here ,f[i][j-i] The capacity of the backpack is j-i, Item quantity or 1,2,3…i, So it's impossible for the backpack to have j-i*(s+1) The situation of .

The optimized state transition equation can also be obtained from the above ：

f[i][j]=f[i-1][j]+f[i][j-i]

One dimensional optimization again ：

f [j]=f [j]+f [j-i]

The code is ：

#include<bits/stdc++.h>

#include<cstring>

#include<algorithm>

#include<math.h>

#include<iostream>

#include<stdio.h>

#include<iomanip>

using namespace std;

typedef long long ll;

const int N=1010;

const int mod=1e9+7;

ll n,f[N];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    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])%mod;

    }

    cout<<f[n]<<endl;

    return 0;

}

 

  expand ：

y There is always another one dp thought , I am directly surprised, sir , Too cattle .

  Code ：

#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdio.h>
#include<iomanip>
using namespace std;
typedef long long ll;
const int N=1010;
const int mod=1e9+7;
ll n,f[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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])%mod;
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod;
    cout<<ans<<endl;
    return 0;
}