题解 | #牛牛的超市#

牛牛的超市

http://www.nowcoder.com/practice/b533bd554baa47d1aa5edff3369bb8d0

描述

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

题解

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

动态规划，但要注意和上楼梯的区别，这个是组合

采用动态规划的方法进行求解：

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

记 $dp[i][j]$ 表示用前 $i$ 种货币凑出金额为 $j$ 的方案数量，

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

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

对于每个dp 在遍历的过程中有

$dp[i+1][j+k*a[i][0]]=dp[i+1][j+k*a[i][0]]+ dp[i][j]$

约束条件为
$k <= a[i][1]$ 和 $j+k*a[i][0] <= x $

即满足钱数不超过目标钱数每种零钱有数量限制

图解如下：

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];
    }
};

复杂度分析：

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

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

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

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

前面的方法主要是利用小钱的方案数去递归得到大钱的方案数，那么如果事先记录每个小钱的方案数再反推大的方案数就可以省掉一重存储空间

本质上是每轮循环都暂存了

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

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];
    }
};

复杂度分析：

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

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