POJ.3181 Dollar Dayz

Problem:
http://poj.org/problem?id=3181

Idea:
Exactly same as knapsack problem with no limit.
dp[i][j]: number of the ways of making j with first i elements.
 - dp[i][j] = dp[i - 1][j] (a[i] > j)
 - dp[i][j] = dp[i - 1][j] + dp[i][j-a[i]] (otherwise)
* the poj judge requires big int test pass, even long long is not possible to get AC.

Source

 ll dp[111][1111];  
 int n, k;  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 1; i <= n; i++) dp[1][i] = 1;  
      for (int i = 2; i <= k; i++)  
           for (int j = 1; j <= n; j++) {  
                if (j < i) dp[i][j] = (dp[i-1][j]) % 1000000000;  
                else if(j == i) dp[i][j] = (dp[i - 1][j] + 1) % 1000000000;  
                else dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % 1000000000;  
           }  
      cout << dp[k][n] << endl;  
      return 0;  
 }