Thoughts
Here the problem is POJ.
The number of ways to buy total $N by the combination of $1~$K.
The first thought is if I can compose $5, I can also compose $5+1 or $5+2 til $5+K.
However, the problem needs to know how many ways.
So, I try to draw a form NxK and fill it to know what I will think when I do so.
And, I am lazy, so I prefer to find the general rules to fill.
It’s the part I like DP (also Greedy) and I won’t draw it again(?).
題目所求為用$1~$K組出$N有幾種組合。
第一個想法是，當我能夠組出$5時，我同時可以組出$5+1或$5+2..或$5+K。
但題目問的是有幾種。
因此試著畫NxK的表格，並將它填滿。
在填表格的時候我會去記我的想法，或者說，找出該格的最佳解可以（最好）由哪些組成。
最好能夠找出共通點。
這部分是我喜歡DP原因，所以我不會畫出來的(?)。
Anyway, I find that if I want to $i to compose $j, it’s the best to take the number of ways of $j(that I want to compose)-$i in each $1~i.
That is, if I use $1 to compose $2, the number of ways is 1.
Use $2 to compose $2, the number will be 2.
Then use $3 to compose $5, there are two ways to compose.
One is (1, 1, 2). The other is (2, 3).
So try to use adding the number of ways of $1 to compose $2 and $2 to compose $2.
總之，每一格都有著一個共通點是，當我要用$i組出$j時，最好的辦法是拿從$1~$i裡組出$j-i的數。
用$1組$2，方法是1。
用$2組$2，方法是1。
當用$3組$5時，方法會是2。
（1, 1, 3）或者是（2, 3）。
這會造成每次都要刷過一次$1~i。
那麼就試著將他們加起來呢？
It’s totally fine.
這是可以的。 （可以可以。可以可以。放心可以。）
DP
dp[i][j] = dp[i][j - i] + dp[i - 1][j];
dp[i][j] is the number of ways to compose $j by using $1~i.
dp[i][j]是用$1~i組出$j方法數的最佳解。
Addition
However, I got WA.
And the reason is the answer is more than 64 bits.
只是我吃WA了。
原因是因為這題答案會大於64 bits。ˊ_>ˋ
不知道有沒有人能夠告訴我怎麼在想得時候就發現呢
Code
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
char dp[105][1005][50];
void ADD(int Xi, int Xj, int Yi, int Yj){ //big int addition, 大數加法
int i, j, l = strlen(dp[Xi][Xj]), L = strlen(dp[Yi][Yj]);
char a, b;
for(i = j = 0; i < l || i < L; i++){
a = dp[Xi][Xj][i]; b = dp[Yi][Yj][i];
if(i >= l) a = '0';
else if(i >= L) b = '0';
j += (int)(a - '0' + b - '0');
dp[Xi][Xj][i] = (char)(j % 10 + '0');
j /= 10;
}
if(j) dp[Xi][Xj][i] = (char)(j % 10 + '0');
}
int main(void){
int N, K, i, j;
scanf("%d %d", &N, &K);
for(i = 1, dp[0][0][0] = '1'; i <= K; i++){ //DP
for(j = 0; j <= N; j++){
if(j - i >= 0) ADD(i, j, i, j - i);
ADD(i, j, i - 1, j);
}
}
for(i = strlen(dp[K][N]) - 1; i >= 0; i--) printf("%c", dp[K][N][i]);
printf("\n");
}