找零问题的方案数（背包问题）

class Solution {
    /**
     * 换零钱方案数
     * @param coins 零钱种类
     * @param total 总钱数
     * @return 总的方案数
     */
    public int exchange(int [] coins,int total) {
        int [][]dp = new int[coins.length+1][total+10];
        //int coins[]={1,2,5,10};
        int size=coins.length;

        for (int i = 0; i <= size; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= size; i++) {
            for (int j = 0; j <= total; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[size][total];
    }

};