LeetCode322零钱兑换

标签: leetcode刷题笔记

零钱兑换
在这里插入图片描述

dp[i]i元至少需要多少个硬币个数,则其前一个状态位使用现有硬币的情况下至少需要多少硬币 dp[i-coins[j]],dp[i]=min(dp[i-coins[j]+1

package BDyNamicProgramming;

import AarrayProblem.Problem1;

/**
 * @Author Zhou  jian
 * @Date 2020 ${month}  2020/4/21 0021  18:47
 * 零钱兑换
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额,返回 -1。
 */
public class Problem322 {

    /**
     * dp[n]为凑成n源所需要的最少硬币个数
     * dp[n] =   Math.min(dp[n-i])+1 i为所有的比值
     * dp[0]= 0  dp[1]
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {



        int[] dp = new int[amount+1];
        //凑成0元需要0个硬币
        dp[0]=0;

        for(int i=1;i<=amount;i++){
            //最少的个数
            int min = Integer.MAX_VALUE;
            //从硬币中挑选(挑选某个硬币之后
            for(int j=0;j<coins.length;j++){

                //假如硬币的值与需要凑的前相等则直接为1
                if(coins[j]==i) {
                    min=1;
                    break;
                }

                //凑成i元的最小值 为  从i-coins[j]
                if(i-coins[j]>=0&&dp[i-coins[j]]!=-1) //可以凑的话
                min = Math.min(min,dp[i-coins[j]]+1);

            }
            //凑不出来的话
            if(min==Integer.MAX_VALUE){
                dp[i]=-1;
            }else {
                //最少的个数
                dp[i] = min;
            }
        }
        return dp[amount];
    }


    public static void main(String[] args) {

        int[] coins = {2};
        Problem322 problem322 = new Problem322();
        int size =problem322.coinChange(coins,3);
        System.out.println(size);
    }
}



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

智能推荐

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. 修改变量...