# 題目: 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)
dp[i][j] 記得要 &= 1000000
# 參考程式碼
#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/
