给一个int []整数数组,[2,7,3,5,3]会有重复值，现在给aim=10，组成10最少用多少个硬币？

    1.     public static int coinsWay1(int[] arr, int aim) {
    2.         if (arr == null || arr.length == 0 || aim < 0) {
    3.             return 0;
    4.         }
    5.         return process1(arr, 0, aim);
    6.     }
    8.     // 暴力递归
    9.     // arr[index...]组成rest这么多钱，最少的硬币数量返回。
    10.     // arr硬币都在里面 
    11.     // index:自由选择arr[index...]
    12.     // rest：剩余到达成的目标
    13.     // 组成rest这么多钱，返回最少的硬币数
    14.     public static int process1(int[] arr, int index, int rest) {
    15.         if(rest < 0){
    16.             return     -1;  // 代表到最后怎么都组成都组成不了
    17.         }
    19.         if(rest == 0){
    20.             return 0;  // 说明已经搞定了aim，需要0枚
    21.         }
    22.         // rest>0情况
    23.         // index == arr.length 没有硬币了，没有这样的方案
    24.         if(index == arr.length){
    25.             return -1; 
    26.         }
    27.         // rest>0，并且也有硬币
    28.         // 不选择当前硬币，和选择当前硬币
    29.         // 不选择index硬币
    30.         int p1 = process1(arr, index + 1, rest);
    31.         // 选择当前硬币
    32.         int p2Next = process1(arr, index + 1, rest - arr[index]);
    34.         if(p1 == -1 && p2Next == -1){
    35.             return -1;
    36.         }else{
    37.             if(p1 == -1){   // 决策p1无效，返回p2 , +1是因为用了当前idnex硬币
    38.                 return p2Next + 1;
    39.             }
    40.             if(p2Next == -1){ // 决策p2无效，返回p1
    41.                 return p1;
    42.             }
    44.             return Math.min(p1, p2Next+1); // 都有效，决策选择出用的硬币最少的,无效解-1会干扰决策
    45.         }
    47. //      不能这样,等于-1时会影响到决策        
    48. //        return Math.min(process1(arr, index + 1, rest), 
    49. //                    1 + process1(arr, index + 1, rest - arr[index]));
    51.     }
    53.     // 记忆化搜索，搞定可变参数组合  
    54.     public static int coinsWay2(int[] arr, int aim) {
    55.         if (arr == null || arr.length == 0 || aim < 0) {
    56.             return 0;
    57.         }
    58.         int [][] dp =new int [arr.length+1][aim+1];
    59.         for (int i = 0; i <= arr.length; i++) {
    60.             for (int j = 0; j <= aim; j++) {
    61.                 dp[i][j] = -2; //表示没计算过
    62.             }
    63.         }
    64.         return process2(arr, 0, aim, dp);
    65.     }
    67.     // arr硬币都在里面
    68.     // index:自由选择arr[index...]这些硬币
    69.     // rest：剩余到达成的目标
    70.     // 组成rest这么多钱，返回最少的硬币数
    71.     public static int process2(int[] arr, int index, int rest,int[][] dp) {
    73.         // 认为中了无效缓存
    74.         if(rest<0){
    75.             return     -1; // 直接放前面，也算一种缓存
    76.         }
    78.         if(dp[index][rest]!= -2){
    79.             return dp[index][rest];
    80.         }
    82.         if(rest==0){
    83.             dp[index][rest]=0; 
    84.         }else if(index == arr.length){
    85.             // rest>0,没有硬币
    86.             dp[index][rest]=-1; 
    87.         }else{
    88.             int p1 = process2(arr, index + 1, rest,dp);
    89.             int p2Next = process2(arr, index + 1, rest - arr[index],dp);
    90.             if(p1 == -1 && p2Next == -1){
    91.                 dp[index][rest]=-1; 
    92.             }else{
    93.                 if(p1 == -1){   // 决策p1无效，返回p2
    94.                     dp[index][rest]= p2Next + 1;
    95.                 }else if(p2Next == -1){ // 决策p2无效，返回p1
    96.                     dp[index][rest]= p1;
    97.                 }else{
    98.                     dp[index][rest]= Math.min(p1, p2Next+1); // 都有效，决策    
    99.                 }
    100.             }
    102.         } 
    103.         return dp[index][rest];
    104.     }
    106.     // 动态规划
    107.     public static int coinsWay3(int[] arr, int aim) {
    108.         if (arr == null || arr.length == 0 || aim < 0) {
    109.             return 0;
    110.         }
    111.         int N=arr.length;
    112.         int [][] dp =new int [N+1][aim+1];
    113.         // base case
    114.         for (int row = 0; row <= N; row++) {
    115.             dp[row][0]=0;
    116.         }
    117.         // base case    
    118.         for (int col = 1; col <= aim; col++) {
    119.             dp[N][col] = -1;
    120.         }
    122.         // n行填好， 从n-1行开始，从左往右，从下向上
    123.         for (int index = N-1; index >=0; index--) {
    124.             // 0列填好，从开始
    125.             for (int rest = 1; rest <= aim; rest++) {
    126.                 // 把递归代码黏贴过来改
    127.                 // 递归过程变成了，动态规划格子取值过程
    128.                 int p1 = dp[index+1][rest];
    129.                 int p2Next = -1; // 越界-1 ，没越界赋值,注意边界
    130.                 if(rest - arr[index]>=0){  // [rest - arr[index]]可能越界所以要这样写
    131.                     p2Next = dp[index+1][rest - arr[index]]; 
    132.                 }
    134.                 if(p1 == -1 && p2Next == -1){
    135.                     dp[index][rest] = -1;
    136.                 }else{
    137.                     if(p1 == -1){   // 决策p1无效，返回p2
    138.                         dp[index+1][rest]= p2Next + 1;
    139.                     }
    140.                     if(p2Next == -1){ // 决策p2无效，返回p1
    141.                         dp[index+1][rest]= p1;
    142.                     }
    143.                     dp[index+1][rest]= Math.min(p1, p2Next+1); // 都有效，决策    ,因为最后一行是-1还是有干扰
    144.                 }
    145.             }
    146.         }
    148.         // 最终返回
    149.         return dp[0][aim];
    150.     }