描述

这是一篇面对初级coder的题解。
知识点：动态规划
难度：三星

题解

题目：
定义一种新货币，有n(n<=50)种不同的币值，其中币值为 value(value<=50) 的有 w(w<=20) 个。现在你有 x(x<=100) 元，但是你想将 x 元换成若干零钱，请问有多少种换钱的方案？
分析：

记表示用前种货币凑出金额为的方案数量，

初始时，因为每种面值的货币的数量有限，我们要枚举每一个出现的可能数量。

则记第i种货币使用了k个，用前面的数组去推算后面的方案个数

约束条件为
  和

class Solution {
public:
    int solve(int n, int x, vector<vector<int> >& a) {
        vector<vector<int> > dp(n + 1, vector<int>(x + 1, 0));
        dp[0][0]=1;
        for(int i = 0; i < n; i++){ //遍历n种货币
            for(int j = 0; j <= x; j++){ //遍历前j元
                for(int k = 0; k <= a[i][1]; k++){ //枚举第i种货币的个数
                    if(j+k*a[i][0] <= x) //钱数之内
                        dp[i+1][j+k*a[i][0]] += dp[i][j];//动态规划
                    else
                        break;
                }
            }
        }
        return dp[n][x];
    }
};

时间复杂度：，整体逻辑采用了三重循环 k是最大的货币个数

空间复杂度：，即为dp矩阵的大小，除此之外无额外空间

运行测试：
运行时间： 2 ms 占用内存：416K

方法二：一维数组动态规划

上述方法一中，对于，我们每次都用的数据推，因此采用从后往前循环的方式，可以优化掉动态规划的空间。

class Solution {
public:
    int solve(int n, int x, vector<vector<int> >& a) {
        vector<int> dp(x + 1, 0);
        dp[0]=1;//初始化
        for(int i = 0; i < n; i++){ //遍历n种货币
            for(int j = x; j > 0; j--){ //遍历0~j元
                for(int k = 1; k <= a[i][1]; k++){ //枚举第i种货币的个数
                    if(j-k*a[i][0] >= 0) //未达上限
                        dp[j]+= dp[j-k*a[i][0]];//递归·
                    else
                        break;
                }
            }
        }
        return dp[x];
    }
};

时间复杂度：，整体逻辑采用了三重循环 k是最大的货币个数

空间复杂度：，即为dp矩阵的大小，除此之外无额外空间

运行测试：
运行时间 3ms
占用内存 412KB

总结