题解 | #牛牛的超市#

题意整理

有n种不同的货币，给定每种货币的面值和个数。
现在要将x元兑换为这些货币的组合，求总共有多少种方案。

方法一（动态规划）

1.解题思路

这是一个典型的背包问题，x元是背包容量，根据面值以及个数限制逐个推导出每种金额x对应的方案数。

状态定义： $dp[i][j]$ 表示i种币值下，j元的金额有多少换钱方案。
状态初始化：当金额为0元时，所有的状态只有1种方案。
状态转移：每增加一种面额的货币，新增对应的方案数。比如已经计算完货币面额为1元的所有状态，当前货币面额为2元，金额为4元时，如果2元货币为0个，则直接是之前状态为4的情形；如果2元货币为1个，则直接是之前状态为2的情形；如果2元货币为2个，则直接是之前状态为0的情形；将这几种情况累加即是当前金额为4的最终状态。状态方程是 $dp[i][j]=dp[i][j]+dp[i-1][j-k*a[i-1][0]]$ 。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    public int solve (int n, int x, int[][] a) {
        //定义dp数组，dp[i][j]表示i种币值下，j元的金额有多少换钱方案
        int[][] dp=new int[n+1][x+1];
        //只有0元时，统一1种方案
        for(int i=0;i<=n;i++){
            dp[i][0]=1;
        }
        //遍历所有货币
        for(int i=1;i<=n;i++){
            //持有多少钱
            for(int j=1;j<=x;j++){
                //使用多少张a[i-1][0]面值的货币
                for(int k=0;k<=a[i-1][1];k++){
                    if(j-k*a[i-1][0]>=0){
                        dp[i][j]+=dp[i-1][j-k*a[i-1][0]];
                    }
                }
            }
        }

        return dp[n][x];
    }
}

3.复杂度分析

时间复杂度：假设每种硬币数量最多为k个，循环体总共三层，执行次数最多为 $k*x*n$ ，所以最终的时间复杂度是 $O(k*x*n)$ 。
空间复杂度：需要额外大小为 $(x+1)*(n+1)$ 的dp数组，所以空间复杂度是 $O(x*n)$ 。

方法二（状态压缩）

1.解题思路

由于每种状态只与之前对应面值的状态有关，可以考虑只开一维空间。计算的时候需要从后往前推，防止重复计算。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型二维数组 ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    public int solve (int n, int x, int[][] a) {
        //定义dp数组，dp[j]表示j元的金额有多少换钱方案
        int[] dp=new int[x+1];
        //初始化
        dp[0]=1;
        for(int i=0;i<n;i++){
            //从后往前推状态
            for(int j=x;j>0;j--){
                //使用多少张a[i-1][0]面值的货币
                for(int k=1;k<=a[i][1];k++){
                    if(j-k*a[i][0]>=0){
                        dp[j]+=dp[j-k*a[i][0]];
                    }
                }
            }
        }

        return dp[x];
    }
}

3.复杂度分析

时间复杂度：假设每种硬币数量最多为k个，循环体总共三层，执行次数最多为 $k*x*n$ ，所以最终的时间复杂度是 $O(k*x*n)$ 。
空间复杂度：需要额外大小为x+1的dp数组，所以空间复杂度是 $O(x)$ 。