public static int[][] miniCoinDynamic(int[] coin, int sum)
    {
        int len = coin.length;
        int[][] array = init(len, sum);

        for(int i=0; i<len; i++)
        {
            for(int s = 0; s <=sum; s++)
            {
                if( s - coin[i] >= 0)
                {
                    int min = Integer.MAX_VALUE;
                    for(int k=0; k <=i; k++)
                        min = Math.min(min, array[k][s-coin[i]]);
                    array[i][s] = min == Integer.MAX_VALUE ? min: min + 1;
                }
            }
        }

        // find the mini value on the most right column
        int min = Integer.MAX_VALUE;
        for(int k=0; k <len; k++)
            min = Math.min(min, array[k][sum]);
        array[len-1][sum] = min;

        return array;
    }

    public static int[][] init(int height, int width)
    {
        int[][] array = new int[height][width+1];
        for(int i=0; i<height; i++)
        {
            for(int j=0; j<width+1; j++)
            {
                if(j == 0)
                    array[i][j] = 0;
                else
                    array[i][j] = Integer.MAX_VALUE;
            }
        }
        return array;
    }

// CoinChange.java
    // Given coin{2, 3, 4} and s = 6
    // Find the minimum number of coins sums up to s
    public static int minCountWithDynamic(int[] coin, int s, int k, Map<Integer, Integer> map) {
        int min = Integer.MAX_VALUE;
        if(s == 0)
            min = 0;
        else if(s > 0) {
            for(int i=0; i<k; i++) {
                Integer value = map.get(s-coin[i]);
                if(value == null) {
                    int childMin = minCountWithDynamic(coin, s-coin[i], k, map);
                    if(childMin != Integer.MAX_VALUE)
                        min = Math.min(min, childMin + 1);
                } else {
                    min = Math.min(min, value);
                }
                if(s-coin[i] < 0)
                    map.put(s-coin[i], Integer.MAX_VALUE);
                else
                    map.put(s-coin[i], min);
            }
        }
        return min;
    }