题解 | #牛牛的超市#

思路：

题目的主要信息：

有n种不同面值的货币，面值大小和数量记录在数组a中
问将x元换成若干零钱的种类有多少，x可以不为货币面值

方法一：动态规划
具体做法：
使用动态规划，设 $dp[i][j]$ 表示用前 $i$ 种货币凑出金额为 $j$ 的方案数量，初始时 $dp[i][0]=1$ ，因为每种面值的货币的数量有限，我们要枚举每一个出现的可能数量。则用前 $i$ 种货币凑出金额为 $j$ 的方案数等于前 $i-1$ 种面值的货币凑出金额 $j$ 不加入 $k$ 个第 $i$ 种货币的方案数的累加和： $dp[i][j] += dp[i - 1][j - k * a[i - 1][0]]$ ，其中 $j >= k * a[i - 1][0]$ .

class Solution {
public:
    int solve(int n, int x, vector<vector<int> >& a) {
        vector<vector<int> > dp(n + 1, vector<int>(x + 1, 0));//用前i种货币凑出金额为j的方案数量
        for(int i = 0; i <= n; i++)
            dp[i][0]++;  //边界为1
        for(int i = 1; i <= n; i++) //遍历n种货币
            for(int j = 1; j <= x; j++) //遍历前j元
                for(int k = 0; k <= a[i - 1][1]; k++){ //枚举第i种货币的个数
                    if(j >= k * a[i - 1][0])  
                        dp[i][j] += dp[i - 1][j - k * a[i - 1][0]];
                    else
                        break;
                }
        return dp[n][x];
    }
};

复杂度分析：

时间复杂度： $O(nxmax(a[i][1]))$ ，外面两层循环，内循环用最大值来约束。
空间复杂度： $O(nx)$ ，dp矩阵的大小

方法二：动态规划空间优化
具体做法：
上述方法一我们只用到了 $i-1$ 的数据，因此我们可以空间优化这个动态规划使之空间缩小为一维。我们采用从后往前循环，那么遇到 $dp[j]$ 就一定是上一轮 $i-1$ 的 $dp[j]$ ，从后往前不会改变上一轮的值，而从前往后会改变上一轮的值。因此我们可以优化掉动态规划的空间，其他同方法一。
图片说明

class Solution {
public:
    int solve(int n, int x, vector<vector<int> >& a) {
        vector<int> dp(x + 1, 0); //i种面值货币凑出金额为j的方案数目，i可以省去
        dp[0] = 1; //0种货币
        for(int i = 0; i < n; i++){
            for(int j = x; j >= 1; j--){ //逆推
                for(int k = 1; k <= a[i][1]; k++){ //枚举第i种货币的个数
                    if(j >= a[i][0] * k){
                        dp[j] += dp[j - a[i][0] * k];
                    }
                }
            }
        }
        return dp[x];
    }
};

复杂度分析：

时间复杂度： $O(nxmax(a[i][1]))$ ，外面两层循环，内循环用最大值来约束。
空间复杂度： $O(x)$ ，辅助数组dp长度只有 $x+1$