现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值?

问题描述：

        现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，
每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值?

思想：

        我们把这个问题转化为两个子问题，分别为：1>使用n1种普通币（可以重复取），问能用多少种方法拼出m的面值?  2>使用n2种普通币（不可以重复取），问能用多少种方法拼出m的面值? 这两种子问题我们都可以使用动态规划的思想进行解题。

        子问题一：使用n1种普通币（可以重复取），问能用多少种方法拼出m的面值?

•         建立二维数组dp[][]，行表示普通币n1，列表示0~m。dp[i][j]表示使用0~i种普通货币，可以拼出j的面值方法有多少种。
•         二维数组dp[i][0]的第一列表示使用0~i种普通货币，拼出0元的面值方法数。我们可以知道第一列的数值全部为1。
•         二维数组dp[0][j]的第一行表示使用第0号普通货币，拼出j元的面值方法数。由于可以重复使用普通货币，所以只要是0号货币的倍数的钱数方法数全部为1，其他的方法数为0。
•         二维数组dp[i][j]的其他位置的情况可以分为下面几种情况：1>若不使用第i号普通货币，也就是使用0~i-1号货币，获得j元的方法数。2>使用第i号货币1次，获得j-（i号普通货币的面值*1)元的方法数。3>使用第i号货币2次，获得j-（i号普通货币的面值*2)元的方法数。4>.....    我们分析后发现2>---4>的情况的方法数和等于使用0~i种普通货币，可以拼出 j-（普通货币i对应的面值）的面值方法数。

        子问题二：使用n2种纪念币（不可以重复取），问能用多少种方法拼出m的面值? 

•         建立二维数组dp[][]，行表示纪念币n2，列表示0~m。dp[i][j]表示使用0~i种纪念货币，可以拼出j的面值方法有多少种。
•         二维数组dp[i][0]的第一列表示使用0~i种纪念货币，拼出0元的面值方法数。我们可以知道第一列的数值全部为1。
•         二维数组dp[0][j]的第一行表示使用第0号纪念货币，拼出j元的面值方法数。由于不可以重复使用纪念货币，所以只要是0号货币的钱数方法数全部为1，其他的方法数为0。
•         二维数组dp[i][j]的其他位置的情况可以分为下面几种情况：1>若不使用第i号纪念货币，也就是使用0~i-1号货币，获得j元的方法数。2>使用第i号货币，获得j-（i号普纪念币的面值)元的方法数。

        这两个子问题全部解决后，我们就可以遍历从而得出最后的方法数。

代码

    public static int moneyWays(int[] arbitrary,int[] onlyone,int money){
        if (money<0){
            return 0;
        }
        if ((arbitrary==null||arbitrary.length==0)&&(onlyone==null||onlyone.length==0)){
            return money==0?1:0;
        }
        //任意张 的数组，一张的数组，不可能都没有
        int[][] dparb = getDpArb(arbitrary,money);
        int[][] dpone = getDpOne(onlyone,money);
        if (dparb==null){//任意张的数组没有，一张的数组有
            return dpone[dpone.length-1][money];
        }
        if (dpone==null){
            return dparb[dparb.length-1][money];
        }
        int res = 0;
        for (int i =0;i<=money;i++){
            res += dparb[dparb.length-1][i]*dpone[dpone.length-1][money-1];
        }
        return res;
    }
 
    public static int[][] getDpArb(int[] arr,int money){
        if (arr==null||arr.length==0){
            return null;
        }
        int[][] dp = new int[arr.length][money+1];
 
        for (int i =0;i
            dp[i][0] = 1;
        }
        for (int j=1;arr[0]*j<=money;j++){
            dp[0][arr[0]*j] = 1;
        }
 
        for (int i =1;i
            for (int j =1;j<=money;j++){
                dp[i][j]=dp[i-1][j];
                dp[i][j]+=j - arr[i]>=0?dp[i][j-arr[i]]:0;
            }
        }
        return dp;
    }
 
    public static int[][] getDpOne(int[] arr,int money){
        if (arr==null||arr.length==0){
            return null;
        }
        int[][] dp = new int[arr.length][money+1];
        for (int i =0;i
            dp[i][0] = 1;
        }
        for (int i =0;i<=money;i++){
            dp[0][i] = arr[0] == i?1:0;
        }
        for (int i =1;i
            for (int j = 1;j<=money;j++){
                dp[i][j] = dp[i-1][j];
                dp[i][j]+=j-arr[i]>=0 && i-1>=0?dp[i-1][j-arr[i]]:0;
            }
        }
        return dp;
    }