[Coding Made Simple] Coin Changes Number of ways to get a total

时间：2017-08-18 14:05:40 阅读：329 评论：0 收藏：0 [点我收藏+]

Given coins of certain denominations and a total, how many ways these coins can be combined to get the total.

Dynamic Programming solution

State: T[i][j]: given the first i coins, the total number of ways these coins can be combined to get the total j.

Function: T[i][j] = T[i - 1][j] + T[i][j - coins[i - 1]], if j >= coins[i - 1];

　　　　 T[i][j] = T[i - 1][j], if j < coins[i - 1];

Initialization:

if the total is 0, then T[i][0] = 1,i is from 0 to coins.length; the only way is to not select any coins;

if there is no coins to select from, then T[0][j] = 0, j is from 1 to total, as there is 0 way to get a non zero total if we have no coins to select from;

Answer: T[coins.length][total];

 1 public class CoinChange {
 2     public int minCoinsToGetTotal(int[] coins, int total) {
 3         if(total == 0) {
 4             return 1;
 5         }
 6         if(total != 0 && (coins == null || coins.length == 0)) {
 7             return 0;
 8         }
 9         int[][] T = new int[coins.length + 1][total + 1];
10         for(int j = 0; j < T[0].length; j++) {
11             T[0][j] = 0;
12         }
13         for(int i = 0; i < T.length; i++) {
14             T[i][0] = 1;
15         }
16         for(int i = 1; i < T.length; i++) {
17             for(int j = 1; j < T[0].length; j++) {
18                 if(j >= coins[i - 1]) {
19                     T[i][j] = T[i - 1][j] + T[i][j - coins[i - 1]];
20                 }
21                 else {
22                     T[i][j] = T[i - 1][j];
23                 }
24             }
25         }
26         return T[coins.length][total];
27     }
28 }