* k|coin 1  3  5  min
  * 0    0  0  0  0
  * 1    1  0  0  1
  * 2    2  0  0  2
  * 3    3  1  0  3, 1
  * 4    2  2  0  2, 2
  * 5    3  3  1  3, 3, 1
  * 6    2  2  2  2, 2, 2
  * ...

public static int backTrackingCoin(int[] coins, int k) {//回溯法+动态规划
    if (coins == null || coins.length == 0 || k < 1) {
      return 0;
    }
    int[][] matrix = new int[k + 1][coins.length + 1];
    for (int i = 1; i <= k; i++) {
      for (int j = 0; j < coins.length; j++) {
        int preK = i - coins[j];
        if (preK > -1) {//只有在不小于0时, preK才能存在于数组matrix中, 才能够进行回溯.
          matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在进行回溯
          if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果当前的硬币数目是最少的, 更新min列的最少硬币数目
            matrix[i][coins.length] = matrix[i][j];
          }
        }
      }
    }
    return matrix[k][coins.length];
  }