一个int数组，里面无重复值，可以使用其中任意张，aim=10，用任意面值任意张，问方法数是多少？

    1.     public static int way1(int []arr,int aim){
    2.         return process(arr,0,aim);
    3.     }
    4.     // 暴力递归    
    5.     // 可以自由使用arr[index...]所有的值  index
    6.     // 需要搞定的钱数是rest
    7.     // 返回找零的方法数
    8.     public static int process(int []arr,int index,int rest){
    9.         if(index==arr.length){ // 没有面值可以选了
    10.             return rest == 0 ? 1: 0; // 要搞定剩下的钱数为零，则是一种方法
    11.         }
    12.         // arr[index] 0张、1张...去试，但不要超过rest的数
    13.         int ways=0;
    14.         for (int zhang = 0; arr[index]*zhang <= rest;  zhang++) {
    15.             // 根据当前货币挑出某些位置累加 
    16.             // rest - 已经搞的钱
    17.             ways += process(arr, index + 1, rest - arr[index]*zhang);
    18.         }
    19.         return ways;
    20.     }
    22.     // DP
    23.     // 有枚举行为 时间复杂度为O(aim*index)*O(aim) O(index*aim^2)
    24.     public static int way2(int []arr,int aim){
    25.         if(arr==null || arr.length ==0){
    26.             return 0;
    27.         }
    28.         int N =arr.length;
    29.         int [][] dp= new int [N+1][aim+1];
    31.         dp[N][0] =1;
    33.         for (int index = N-1; index >=0; index--) {
    34.             for (int rest = 0; rest <= aim;rest++) {
    35.                 int ways=0;
    36.                 // 枚举没必要，等于本行向左偏移一位的ways值+下面的值a。
    37.                 for (int zhang = 0; arr[index]*zhang<rest;  zhang++) {
    38.                     // 根据当前货币挑出某些位置累加,把递归行为改成dp中取值
    39.                     ways+=dp[index+1][rest-arr[index]*zhang];
    40.                 }
    41.                 dp[index][rest]=ways;
    43.             }
    44.         }
    45.         return dp[0][aim];
    46.     }
    48.     // 优化完的DP
    49.     // 斜率优化：填表的时候如果有枚举行为，看临近的位置能不能替换枚举行为。只和观察有关，和实际意义无关。统一技巧。
    50.     public static int way3(int []arr,int aim){
    51.         if(arr==null || arr.length ==0){
    52.             return 0;
    53.         }
    54.         int N =arr.length;
    55.         int [][] dp= new int [N+1][aim+1];
    57.         dp[N][0] =1;
    59.         // 自己下方格子的值+加左边格子的值
    60.         // 因为自己左边格子值是枚举来的，不用枚举了
    61.         for (int index = N-1; index >=0; index--) {
    62.             for (int rest = 0; rest <= aim;rest++) {
    64.                 dp[index][rest]=dp[index+1][rest]; // 自己下方格子
    65.                 if(rest - arr[index] >=0){ // 别越界
    66.                                                 // rest减去自己用一张的值偏移
    67.                     dp[index][rest]+= dp[index][rest-arr[index]]; // 自己本行偏移一位的ways值
    68.                 }
    69.             }
    70.         }
    71.         return dp[0][aim];
    72.     }