# 題目: UVa 10943 - How do you add

# 題目說明

你需要解決一個計算的問題
給一個最大數N，由小於N的數中取K個數加至N，求有幾種加法?

---

INPUT:
每筆測資輸入兩個整數N、K
當N與K為0時結束程式

---

OUTPUT:
輸出最大數N時，每次取K個數有幾種加法? (dp[N][K])

# 解題方法

同樣將所有情況的答案算出儲存，再根據N, K的值輸出答案

當K = 1時，只有一種可能，所以將dp[i][1]設為1
利用2層for迴圈動態規劃，對於dp[i][j]來說，為dp[i - k][j - 1]的總和 (k為0 ~ i)

# 參考程式碼

#include <iostream>

using namespace std;

int N, K;
int dp[101][101];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);	

	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;

	while (cin >> N >> K, N && K) cout << dp[N][K] << "\n";

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa-10943/