題目

總時(shí)間限制: 200ms 內(nèi)存限制: 65536kB
描述
將正整數(shù)n 表示成一系列正整數(shù)之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整數(shù)n 的這種表示稱為正整數(shù)n 的劃分。

輸入
標(biāo)準(zhǔn)的輸入包含若干組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)是一行輸入數(shù)據(jù),包括兩個(gè)整數(shù)N 和 K。
(0 < N <= 50, 0 < K <= N)
輸出
對(duì)于每組測(cè)試數(shù)據(jù)，輸出以下三行數(shù)據(jù):
第一行: N劃分成K個(gè)正整數(shù)之和的劃分?jǐn)?shù)目
第二行: N劃分成若干個(gè)不同正整數(shù)之和的劃分?jǐn)?shù)目
第三行: N劃分成若干個(gè)奇正整數(shù)之和的劃分?jǐn)?shù)目
樣例輸入
5 2
樣例輸出
2
3
3
提示
第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1

第一問(wèn)

這個(gè)問(wèn)題比之前的整數(shù)劃分問(wèn)題多了一個(gè)限制條件K，可以把這個(gè)問(wèn)題類比為背包問(wèn)題，問(wèn)題轉(zhuǎn)化為如下：
從[1...N]中選擇K個(gè)數(shù)，其和為N，并且選數(shù)可以重復(fù)，這是個(gè)典型的動(dòng)態(tài)規(guī)劃問(wèn)題。
那么考慮子問(wèn)題，從[1...i]中選q個(gè)數(shù)，其和為j.
令f[i][j][q] 表示子問(wèn)題的解。
下面考慮邊界條件：從[1...1]中選擇1 個(gè)數(shù)，其和為1，選法唯一 f[1][1][1] = 1;
接下來(lái)考慮狀態(tài)轉(zhuǎn)移：
f[i][j][q] = f[i-1][j][q] + f[i][j - i][q - 1]
f[i-1][j][q]表示第i個(gè)數(shù)不選，那么要從前i-1個(gè)數(shù)中選q個(gè)，其和為j
f[i][j - i][q-1]表示第i個(gè)數(shù)選，那么從前i個(gè)數(shù)中選q-1個(gè)，其和為j-i，這里i不取i-1是因?yàn)樵谧訂?wèn)題中還會(huì)用到i，即每個(gè)數(shù)選擇不唯一，
這是區(qū)別于一般背包問(wèn)題的特殊情況。
這樣，解這道題使用三位數(shù)組來(lái)記錄動(dòng)態(tài)規(guī)劃過(guò)程就可以了，但是有些動(dòng)態(tài)規(guī)劃是可以使用滾動(dòng)數(shù)組來(lái)節(jié)省空間，這道就可以。
那么假設(shè)一個(gè)二位數(shù)組f[j][q]，用一層循環(huán)表示從前i個(gè)數(shù)中選擇，在第i次循環(huán)開始執(zhí)行前，f[j][q]表示從前i-1個(gè)數(shù)中選q個(gè)湊成j，對(duì)于f[i][j - i][q-1]
因?yàn)樵趂[i][j][q]之前遍歷到，所以f[j-i][q-1]中的值是第i次循環(huán)更新過(guò)的值，這樣一來(lái)，狀態(tài)轉(zhuǎn)移就可以簡(jiǎn)化為：
f[j][q] += f[j-i][q-1]
這部分代碼如下：

dp[0][0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
	for (int q = k; q >= 1; q--)
	    dp[j][q] += dp[j - i][q - 1];
printf("%d
", dp[n][k]);

第二問(wèn)

第二問(wèn)比之前簡(jiǎn)單的整數(shù)劃分問(wèn)題增加了數(shù)字不能重復(fù)的限制，這表現(xiàn)在狀態(tài)轉(zhuǎn)移方程里邊就是：
設(shè)f[i][j]表示從前i個(gè)數(shù)中湊j，
狀態(tài)轉(zhuǎn)移方程為：
f[i][j] = f[i-1][j-i] + f[i-1][j]
同樣，可以用滾動(dòng)數(shù)組將二維轉(zhuǎn)化為一維，注意j要從大到小遍歷
代碼：

dp1[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = n; j >= i; j--)
                dp1[j] += dp1[j - i];
        printf("%d
", dp1[n]);

第三問(wèn)

第三問(wèn)比簡(jiǎn)單的整數(shù)劃分問(wèn)題增加了只能選擇正奇數(shù)，注意，數(shù)字還是可以重復(fù)的，這個(gè)其實(shí)在弄懂了前兩個(gè)題之后就很好寫了
直接寫出狀態(tài)轉(zhuǎn)移方程：
f[i][j] = f[i][j - i] + f[i-2][j]
f[1][1] = 1
用滾動(dòng)數(shù)組的話，i取奇數(shù)遍歷，j需要從小到大遍歷。
代碼：

dp2[0] = 1;
        for (int i = 1; i <= n; i += 2)
            for (int j = i; j <= n; j++)
                dp2[j] += dp2[j - i];
        printf("%d
", dp2[n]);

整道題代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;

const int N = 50 + 5;
int dp[N][N], dp1[N], dp2[N];

int main() {
    for (int n, k; scanf("%d%d", &n, &k) == 2;) {
        memset(dp, 0, sizeof(dp));
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                for (int q = k; q >= 1; q--)
                    dp[j][q] += dp[j - i][q - 1];
        printf("%d
", dp[n][k]);
        dp1[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = n; j >= i; j--)
                dp1[j] += dp1[j - i];
        printf("%d
", dp1[n]);
        dp2[0] = 1;
        for (int i = 1; i <= n; i += 2)
            for (int j = i; j <= n; j++)
                dp2[j] += dp2[j - i];
        printf("%d
", dp2[n]);
    }
    return 0;
}

代碼參考：https://blog.csdn.net/Nightmare_ak/article/details/94414363

總結(jié)

以上是生活随笔為你收集整理的dp算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。