LeetCode-322-零钱兑换

硬币兑换

来源LeetCode, 题目地址<https://leetcode-cn.com/problems/coin-change/>

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

暴力递归(回溯)

每一种硬币都有选择和不选两种情况,因此最简单的方法就是穷举所有可能性,从中找到最小的选择,递归树如下:

2013053-9aa7e116a8c426d9.png
状态树

每次节点的子节点都会出现3个分支,因此时间复杂度是指数级。

尽管明知这个代码是不能通过LeetCode,我还是把代码给写完了。

class Solution1 {
public:
    int MIN_COMB = INT_MAX;
    int coinChange(vector<int>& coins, int amount) {
        DFS(0, amount, coins);
        return MIN_COMB;
    }

    void DFS(int depth, int amount, vector<int>& coins){
        if (amount == 0){
            MIN_COMB = min(depth, MIN_COMB);
            return ;
        }
        for (auto coin : coins){
            if (amount - coin < 0 ) continue; //减枝
            DFS(depth+1, amount - coin, coins);
            
        }
        return ;
    }
};

对于一些比较正常的数据,这个代码都能正常运行,但是对于LeetCode中的[186,419,83,408] 6249,标准答案是20,也就是至少有20层,因此计算量至少是3^20,但是递归深度可以达到75层,计算量就是一个天文数字了。

递归的广度优先搜索

递归树其实是一种深度优先的搜索方法,我们可以采用广度优先搜索方法,对递归树按层进行遍历,第一次遇到amount=0的时候,也就是最小的遍历层数。

class Solution2 {
public:
    int coinChange(vector<int>& coins, int amount) {

        queue<pair<int,int>> q; //level and amount
        q.push({0, amount});

        while ( !q.empty()) {

            int level = q.front().first;
            int surplus = q.front().second;
            q.pop();

            for (auto c : coins){
                if ( surplus - c < 0 ) continue;
                if ( surplus - c == 0 ) return level + 1;
                q.push({level+1, surplus-c});
            }
        }
        return -1;


    }
};

尽管看起来, BFS或许比DFS能够更快的找到最终的解(不需要遍历所有的状态),但是由于递归树本身就是指数增长,因此只要层数过大,时间就会惊人的增长。

你可以保持[1,2,5]不变,然后依次测试,10,20,50,80,100. 你会发现前4个解决速度都比较快,但是到了100,时间就上天了。

贪心算法

暴力递归的问题在于,节点的增长是指数级别的。如果我们每次都选择当前的最优解,也就是对于11,从1,2,5中找交换的硬币的时候,都以5,2,1这种顺序进行选择,就避免了指数级别的增长。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end(), std::greater<>());
        return DFS(0, amount, coins);
    }

    int DFS(int level, int amount, vector<int>& coins){
        if (amount <= 0){
            return amount == 0 ? level : -1;
        }
        for (auto coin : coins){
            int res = DFS(level+1, amount - coin, coins);
            if (res > 0 ) return res;
        }
        return -1;
    }
};

但是贪心算法有一个弊端,你得要证明能够从局部最优一直推导出全局最优解,才能保证你的结果是正确的。如果无法保证,那么贪心算法不一定保证最终结果就是最优解,所以这里贪心算法也是无法通过。

递归+记忆化

在我们之前的递归树中,无论采用何种遍历方式(DFS或BFS),都无法逃脱时间指数级别增长的命运。

不过当我们仔细观察递归树的时候,我们会发现一些节点是被重复计算的。如果能避免这些重复计算,那么时间复杂度就会降低到O(n^2)

在原来递归的代码上加上记忆化,我写了很久,主要是不知道在递归的时候,如何记录当前情况下,如何挑选最优子问题。

先放上正确的答案

class Solution {
public:
    unordered_map<int, int> dict;
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        return DFS(coins, amount);
    }
    int DFS(vector<int>& coins, int amount){
        if (amount < 0 ) return -1;
        if (amount == 0 ) return 0;
        if (dict.find(amount) != dict.end()) return dict[amount];

        int min = INT_MAX; //足够大的值
        for (int coin : coins){
            int res = DFS(coins, amount-coin);
            if (res >= 0 && res < min){
                min = res + 1;
            }
        }
        dict[amount] = (min == INT_MAX ? -1 : min);
        return dict[amount];
    }
};

递归返回的从最后一层到当前层的所需的步数。而之前的递归程代码则是每次记录当前的深度,最终拿深度和全局最小值进行比较。

下面则是我的错误示范。我的代码主题也是想算出最后位置到当前位置的经历的步数,但是我想用最后一层的深度减去当前的深度。结果每一个amount对应都是1.

// 递归+记忆化
class Solution4 {
public:
    unordered_map<int, int> dict;
    int coinChange(vector<int>& coins, int amount) {
    
        return DFS(0, amount, coins);
    }

    int DFS(int depth, int amount, vector<int>& coins){
        if (amount == 0){
            return depth;
        }

        if (dict.find(amount) != dict.end() ) {
            return dict[amount];
        }

        int local_min = INT_MAX;

        for (auto coin : coins){
            if (amount - coin < 0 ) continue; 
            local_min = min(local_min, DFS(depth+1, amount - coin, coins) -depth);
            
        }
        dict[amount] = (local_min == INT_MAX ? -1 :   local_min);
        return dict[amount];
    }
};

自底向上的动态规划

事实上递归加记忆化就是一种动态规划,只不过递归是一种自顶向下的策略。并且有了之前递归加记忆化的经验,我们写递推就变得简单了。

第一步: 定义子问题。我们求解组成金额为n的最少硬币数,也就是求解一系列 n-k (k=coins) 子问题中的最小选择加1。以amount=11,coins=1,2,5为例。求解amount=11的最少硬币,也就是在10,9,6这三种选择中挑选其中所需硬币最小的子问题,然后加1.

第二步:定义DP数组. f(n) = min{f(n-k), k = 1,2,5} + 1

第三步: 定义DP方程: dp[i] = min(dp[i], dp[i-coins[j] ] )+ 1

最终代码如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int MAX = amount + 1;// 只要保证比amount大即可, 因为后续要和当前最小的选择比较。
        vector<int> dp(amount+1, MAX); //DP数组
        dp[0] = 0;
        for (int i = 1; i <= amount; i++){
            for (int j = 0; j < coins.size(); j++){
                if (coins[j] <= i){ //举例, i = 2, 只能考虑coin=1,2, 排除5
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1); 
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

代码中的细节,

  • 初始化的数组大小为amount+1, 不能是amount, 否则只能表示0到amount-1
  • 初始化的数组存放的值,要比最坏情况下的最少硬币数大,例如amount=10, 硬币只有11,那么数组内容就会是原本情况,最终的结果是比amount大,说明无解。因此,MAX = INT_MAX-1 也是可以的。

最终来看,自底向上的动态递归的代码反而是最简洁的。

版权声明:本文为u012110870原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u012110870/article/details/104769515

智能推荐

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

猜你喜欢

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...

rabbitmq五种模式详解(含实现代码)

1.简单模式 当生产端发送消息到交换机,交换机根据消息属性发送到队列,消费者监听绑定队列实现消息的接收和消费逻辑编写.简单模式下,强调的一个队列queue只被一个消费者监听消费. 1.1 结构   生产者:生成消息,发送到交换机 交换机:根据消息属性,将消息发送给队列 消费者:监听这个队列,发现消息后,获取消息执行消费逻辑 1.2应用场景 常见的应用场景就是一发,一接的结构 例如: 手机...

AndroidStudio 常用配置

1. 设置主题&左侧导航栏字体 AndroidStudio->Preferences(下同) 2. 设置字体大小 3. 取消竖线 间距设置大些 4. 控制台字体大小 5. 修改LogCat颜色 LogCat 色值 Verbose BBBBBB Debug 48BB31 Info 0070BB Warn BBBB23 Error FF0006 Assert 8F0005 5. 修改变量...