題目： UVa - 10943 - How do you add?

題目說明

給兩個整數 N、K，求將 N 拆為 K 個小於等於 N 的數字相加的所有情況數。不同排序視為不同情況，如 20 + 0，0 + 20 為兩種情況。

題目看不是很懂，好像計算的時候要隨時取 1000000 的餘數。

Input： 每組測資有兩個整數，依序為 N、K，若 N、K 皆為 0 表結束。

Output： 輸出將 N 拆為 K 個小於等於 N 的數字相加的所有情況數。

解題思路

動態規劃題，由於測資範圍不大，因此先算出所有情況的答案再輸出即可。

定義 dp[i][j] 表 i 拆成 j 個數字的方法數，先設定初始狀態，dp[i][1] = 1, 對於所有 0 <= i < 101，因為任何數拆成一個數字相加只會有一個情況，就是自己。

對於 dp[i][j]:
dp[i][j] = (dp[i][j] + dp[i - k][j - 1]) % 1000000，對於所有 0 <= k <= i。
可以想像為，將 i 拆為 k 及 i - k 相加，而 i - k 由 j - 1 個數字相加組成，這樣組合起來的意義即為使用 j 個數字組合成 i。
簡單來說，就是不斷枚舉加入最後一位數字，並將所有情況數相加即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fMOZjx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int N, K;
int dp[101][101]; // dp[i][j] 表 i 拆成 j 個數字的方法數

void compute()
{
    for (int i = 0; i < 101; ++i) dp[i][1] = 1;
    for (int i = 0; i < 101; ++i) for (int j = 1; j < 101; ++j) for (int k = 0; k <= i; ++k)
        dp[i][j] = (dp[i][j] + dp[i - k][j - 1]) % 1000000;
}

int main()
{
    compute();
    while (cin >> N >> K && N && K) cout << dp[N][K] << '\n';
}

參考資料

UVa 10943 - How do you add?_小白菜又菜-CSDN博客