本篇主要從計數(shù)DP上結(jié)合實例分析。

一、計數(shù)類DP——整數(shù)劃分

整數(shù)劃分大體上可以分為3類

（1）考慮順序的拆分方案（即1，1，2；和2，1，1 是兩種不同的方案），這種問題一般轉(zhuǎn)化為完全背包即可解決。

（2）不考慮順序的拆分方案，可以劃分出空集（也就是可以有對拆分完全沒貢獻(xiàn)的東西存在（0））

（3）不考慮順序的拆分方案，要求劃分出的集合不為空集（不可以拆出0）

主要討論2，3類DP問題

二、空集存在的情況

對于n的m劃分，可以定義dp[m][n]為所求答案， 考慮任意的拆分序列，可以分為兩類

1. 所有都大于0，我們可以每個序列都拿出一個1，則拆分序列變?yōu)?img src="/assets/addons/ueditor/php/upload/image/20221115/1668488640496467.png" title="ai3" alt="ai3" width="17" height="20"/>-1，它的求和為n?m，所以他是n ? m的m劃分 ,對答案的貢獻(xiàn)為dp[i][j-i]。

2. 如果存在=0，可以將之化歸到n的m ? 1劃分，對答案的貢獻(xiàn)為dp[i-1][j]。

從而，有：

dp[i][j]=dp[i?1][j]+dp[i][j?1]

當(dāng)劃分的數(shù)量m太大(m>n)后,第一種情況不存在,

dp[i][j]=dp[i?1][j]

代碼

#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x<<endl;
#define endl '\n'
#define lowbit(x) x&-x
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 200, mod = 1e9 + 7;
int n,m;
ll dp[N][N];// j 的 i劃分
void solve()
{    
    cin >> n >> m;
    // dp[i][j] = dp[i-1][j] + dp[i][j - i] 
    dp[0][0] = 1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(j - i >= 0){
                dp[i][j] = dp[i][j-i] + dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[m][n] << endl;
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}

三、空集不存在的情況

在原來的基礎(chǔ)上只要解決了重復(fù)計數(shù)的部分即可，顯然就是不在考慮中存在0的情況，把上面代碼else去掉。

并且注意初始化dp時,初始化為dp[m][0] = 1 ,防止重復(fù)計算

代碼如下：

#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x<<endl;
#define endl '\n'
#define lowbit(x) x&-x
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =10 + 200, mod = 1e9 + 7;
int n,m;
ll dp[N][N];// j 的 i劃分
void solve()
{    
    cin >> n >> m;
    // dp[i][j] = dp[i-1][j] + dp[i][j - i] 
    dp[0][m] = 1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j - i >= 0){
                dp[i][j] = dp[i][j-i] + dp[i-1][j];
            }
        }
    }
    cout << dp[m][n] << endl;
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}