322. Coin Change 新手可学,从此再也不愁找零钱问题 动态规划教程


题目意思是,给一个面值数组,求组成某个金额最少需要多少纸币。
这题其实我刚开始是没放在眼里的,随意写了些,结果。。。

TIM截图20180411120902.png


事实又一次说明,刷的题再多(LeetCode 200 ,AC率47%),问题没搞明白那都是不行的,简单的问题深刻起来也是不简单的。

好了,言归正传,这道题目有两个状态,一个是n个面值,一个是总额m,对于非老司机来说,肯定首先想到的是用一个n*m的二位数组表示所有状态。然而,不论是LeetCode的Discuss还是网上的博客,都是最终滚动数组优化的版本(dp过程只用了一个一维数组),省略了中间的思考优化过程,对于新手的进阶来说,是非常不利的。所以,我手动实现了二维数组的版本,在讲解后给大家附上了代码。

我们用到的样例是面值数组coins=[2, 5, 1], 总额amount = 11,此时n=3, m=11;我们用dp[m][n]来表示所有可能的状态,dp[i][j]表示,用前i(0 <= i < n)个面值,表示总额j(0 <= j <= m),需要纸币的最少数目。

所谓动态规划,就是把大问题逐步分解成容易解决的最基础的小问题,然后通过寻找最基础的问题和大问题的关系,找到大问题的解。那么我们接下来开始解决最基础的小问题。
j=0,就是要组成的总额为0时,就是j最基本的问题了,很明显,需要0张2,0张5,0张1也就是说dp[i][0] = 0 (0 <= i < n);
代码也很容易,如下:
        for (int i = 0; i < n;  ++i){
            dp[i][0] = 0;
        }


j最基础的问题解决了,那i呢?很明显,i 什么都没有同样是最基本的问题,但你不觉得写个循环初始化全部j=0(j什么都没有)的状态为0,再写个循环把i什么都没有的状态都初始化为0太过分了吗?
所以,我们就解决一下i=coins[0](i = 0),i只有一个值这个子问题,也就是说考虑只有面值数组中第一个面值的情况,既:面值为2的纸币(在面值数组中下标为0),凑够m=11,最少需要多少。
好了,现在开始,j从1开始循环(0已经在之前初始化了),
j=1时,面值为2的不可能凑到1,所以dp[0][1] = inf(大于inf表示不存在);
j=2时,相当于用2凑够面值为0(2 - 2 = 0)的最小数目加1
j=3时,相当于用2凑够面值为1(3 - 2 = 1)的最小数目加1
j=4时,相当于用2凑够面值为2(4 - 2 = 2)的最小数目加1
...
j=时,相当于用2凑够面值为n-2的最小数目加1
没看懂没关系,我后面附上了模拟的表格,模拟模拟就好了。
这部分对应step1部分:

微信图片_20180411130532.jpg


这样我们就找到了第一个状态转移式子dp[0][j-2]可以转移到dp[0][j],转移方式是加一张两块纸币,因为我们要的是最小,所以我们得到了一个式子:
dp[0][j] = min(dp[0][j], dp[0][j - 2]  + 1);
推广一下,容易得到
dp[0][j] = min(dp[0][j], dp[0][j - coins[0]]  + 1);//本例中coins[0]=2,就是替换回了原本形式。


代码也容易写:
        for (int j = 1; j <= amount; ++ j){
            if (j - coins[0] >= 0){
                dp[0][j] = min(dp[0][j - coins[0]]  +  1, dp[0][j]);
            } 
        }


好了,那么i=coins[0](i=0)的问题解决了,那么i= 1,2,,..n的问题,肯定也是从上面这个问题来的,怎么来的呢?
想一下,在某个面值做选择时,只有两种可能,我用这个面值,和我不用这个面值:
我用这个面值,就和前面一样了:
dp[i][j] = dp[i][j - coins[i]] + 1;
我不用这个面值,那我就直接继承之前的状态:
dp[i][j] = dp[i - 1][j];
总共就这两种可能,我就选个最小的就好了,因为答案需要最少的数量嘛,所以这一步的转移方程:
dp[i][j] = min(dp[i][j - coins[i]] + 1, dp[i - 1][j]);
这部分对应step2和step3

代码也就好写了

        for (int i = 1; i < n;   ++i){
            for (int j = 1; j <= amount;  ++ j){
                if (j - coins[i] >= 0){
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]]  + 1);
                }else{
                    dp[i][j] = dp[i - 1][j];//如果j小于当前面值,那明显不能用当前面值,只能继承前面的,模拟一下就懂啦~
                }
            }
        }

有同学很好奇,如何反应一张面额可以用多次,如果你有模拟我上传的那张纸图,你会发现j=x的时候你可以选择用当前面值,j=x加1你还可以选择用。。。

好了,最后上AC代码(时间O(m*n),空间O(m*n)):
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size(), m = amount;
        if (n == 0 || m == 0){
            return 0;
        }
        
        dp.resize(n + 1, vector<int>(m + 1, 0x7ffffff));
        
        for (int i = 0; i < n; ++i){
            dp[i][0] = 0;
        }
        
        for (int j = 1; j <= amount; ++j){
            if (j - coins[0] >= 0){
                dp[0][j] = min(dp[0][j - coins[0]] + 1, dp[0][j]);
            } 
        }
        
        for (int i = 1; i < n; ++i){
            for (int j = 1; j <= amount; ++j){
                if (j - coins[i] >= 0){
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][m] >= 0x7ffffff ? -1 : dp[n - 1][m];
    }
private:
    vector<vector<int>> dp;
    int result = 0;
};


然后这个最容易想到的思路就搞定了,那么怎么把空间优化到O(m)呢?
观察我们的状态转移方程dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1);你会发现,只用到了i和i-1这两行,i-2行以前的以后就再也不用了,也就是说,可以省掉。。。怎么省呢?
计算行的时候%2,i是这一行,i-1就是另一行,就这么轮番用。。。
于是,所谓的滚动数组,就这么搞定啦:
AC代码
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size(), m = amount;
        if (n == 0 || m == 0){
            return 0;
        }
        
        dp.resize(2, vector<int>(m + 1, 0x7ffffff));
        
        for (int i = 0; i < n; ++i){
            dp[i % 2][0] = 0;
        }
        
        for (int j = 1; j <= amount; ++j){
            if (j - coins[0] >= 0){
                dp[0][j] = min(dp[0][j - coins[0]] + 1, dp[0][j]);
            } 
        }
        
        for (int i = 1; i < n; ++i){
            for (int j = 1; j <= amount; ++j){
                if (j - coins[i] >= 0){
                    dp[i % 2][j] = min(dp[(i - 1) % 2][j], dp[i % 2][j - coins[i]] + 1);
                }else{
                    dp[i % 2][j] = dp[(i - 1) % 2][j];
                }
            }
        }
        return dp[(n - 1) % 2][m] >= 0x7ffffff ? -1 : dp[(n - 1) % 2][m];
    }
private:
    vector<vector<int>> dp;
    int result = 0;
};


同样的思路,再把这两行优化成一行(本质上说,不重要):
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size(), m = amount;
        if (n == 0 || m == 0){
            return 0;
        } 
        
        dp.resize(amount + 1, 0x7ffffff);
        dp[0] = 0;
        for (int i = 0; i < n; ++i){
            for (int j = 1; j <= amount; ++j){
                if (j - coins[i] >= 0){
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[m] >= 0x7ffffff ? -1 : dp[m];
    }
private:
    vector<int> dp;
};


相信这些都理解的话,其他写法,大家也都会看明白啦~~码字不易啊,中午饭都忘吃了Orz。

1 个评论

赞的
不过 以后发问题 更好哈

要回复文章请先登录注册

返回顶部