dp-划分数（递推）

问题描述：

　　有 n 个无区别的物品 , 将他们分成不超过 m 堆，问有多少种分法？　　

例如：

　　n = 4 , m = 3 , 则总共有的分法是 1 + 2 +1 , 0 + 1 + 3 , 0 + 2 + 2 , 0 + 0 + 4 。

　　共有 4 种分法，观察这四种分法，有一个特点，即带 0 的划分和不带 0 的划分，首先不带 0 的划分，比如 1 + 2 + 1 就可以视为是 0 + 1 + 0 的划分数递推加 1 得到的，带 0 的划分就可以视为是将 n 分为 m - 1 份所得到的划分数。

代码示例：

int n, m;

int dp[100][100];

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    cin >> n >> m;

    dp[0][0] = 1;

    for(int i = 1; i <= m; i++) dp[0][i] = 1;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if (i >= j) dp[i][j] = dp[i-j][j]+dp[i][j-1];

            else dp[i][j] = dp[i][j-1];

        }

    }

    cout << dp[n][m] << endl;

    return 0;

}

将数字 n 分成不超过 m 份的方案数

dp[i][j] 表示将数字 i 分成 j 份的方案数，转移的话分为两种，

第一种是假设其中有某一堆的个数为 1 ，则可以有 dp[i-1][j-1] 推来

第二种是假设其中所有堆的个数都大于等于 2, 则可以由 dp[i-j][j] 推来

int n, m;

int dp[205][100];

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    cin >> n >> m;

    dp[0][0] = 1;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if (i >= j) dp[i][j] = dp[i-j][j]+dp[i-1][j-1];

        }

    }

    cout << dp[n][m] << endl;

    return 0;

}

巴特西

dp-划分数（递推）

最新文章

热门文章

巴特西

dp-划分数 （递推）

最新文章

热门文章

dp-划分数（递推）