Pages

Monday, September 7, 2015

Count Posibble Coin Changing Problem (Dynamic Programming)

From previous "Count Posibble Coin Changing Problem (Recursive)"


 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
30
31
32
33
34
35
36
37
38
39
public class HelloWorld {

 public static void main(String[] args) {
   int[] arr = {5,37,8,39,33,17,22,32,13,7,10,35,40,2,43,49,46,19,41,1,12,11,28};
   int m = (int)arr.length;
   int n = 166;
   System.out.print(" " + count(arr, m, n) + " ");
 }
public static int count(int[] s, int m, int n) { long x, y; // We need n+1 rows as the table is constructed in bottom up manner using // the base case 0 value case (n = 0) long[][] coins = new int[n + 1][m]; // Fill the entries for 0 value case (n = 0) for(int i = 0; i < m; i++) { coins[0][i] = 1; } // Fill rest of the table entries in bottom up manner for(int i = 1; i < n + 1; i++) { for(int j = 0; j < m; j++) { // Count of solutions including S[j] x = i - s[j] >= 0 ? coins[i - s[j]][j] : 0; // Count of solutions excluding S[j] y = j >= 1 ? coins[i][j - 1] : 0; // total count coins[i][j] = x + y; } } return coins[n][m - 1]; } }

No comments:

Post a Comment