【Java每日一题,动态规划,零钱兑换模板题】硬币组合数量

简介: 【Java每日一题,动态规划,零钱兑换模板题】硬币组合数量

Introduction

给你一个非负整数n,再给你一个整数数组nums表示不同面值的硬币。


请你计算并返回可以凑成总金额n的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。


假设每一种面额的硬币有无限个。


n和nums都在int整数范围内


Input

第一行输入整数n和m。n表示总金额数(1<=n<=10000),m表示数组的元素个数。(1<=m<=10)


第二行输入互不相同的m个整数表示不同面值的硬币,每个数字用空格隔开。硬币面值不大于10000


Output

输出可以凑成总金额的硬币组合数


Sample

input

5 3
1 2 5

output

4

Solution

import java.util.Scanner;
public class Main {
    static int n,m,ans=0;
    static int[] arr;
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
         n=s.nextInt(); m=s.nextInt();
         arr=new int[m];
         for(int i=0;i<m;i++){
             arr[i]=s.nextInt();
         }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : arr) {
            for (int i = coin; i <= n; i++) {
                dp[i] += dp[i - coin];
            }
        }
        System.out.println( dp[n]);
    }
}

Experience

刚开始想的是完全背包问题,感觉有些出入。通过类似的动态规划,然后就能求解出。

它的一维优化,和完全背包问题的一维优化类似。

相关文章
|
7月前
|
Java
0-1背包问题(Java详解)(动态规划)至少与恰好
0-1背包问题(Java详解)(动态规划)至少与恰好
60 1
|
7月前
|
Java
有关Java发送邮件信息(支持附件、html文件模板发送)
有关Java发送邮件信息(支持附件、html文件模板发送)
431 1
|
7月前
|
Java
java发送微信公众号模板消息
java发送微信公众号模板消息
|
2月前
|
搜索推荐 Java 数据库连接
Java|在 IDEA 里自动生成 MyBatis 模板代码
基于 MyBatis 开发的项目,新增数据库表以后,总是需要编写对应的 Entity、Mapper 和 Service 等等 Class 的代码,这些都是重复的工作,我们可以想一些办法来自动生成这些代码。
36 6
|
2月前
|
算法 Java Linux
java制作海报四:java BufferedImage 转 InputStream 上传至OSS。png 图片合成到模板(另一个图片)上时,透明部分变成了黑色
这篇文章主要介绍了如何将Java中的BufferedImage对象转换为InputStream以上传至OSS,并解决了png图片合成时透明部分变黑的问题。
84 1
|
2月前
|
Java
Java PDF模板生成PDF
Java PDF模板生成PDF
46 1
|
7月前
|
存储 Java
Dijkstra最短路径(Java)(详细+模板)
Dijkstra最短路径(Java)(详细+模板)
72 4
|
7月前
|
机器学习/深度学习 算法 Java
全排列(分治)(Java语言 +全排列模板)
全排列(分治)(Java语言 +全排列模板)
43 2
|
2月前
|
小程序
java--微信小程序发送模板消息
java--微信小程序发送模板消息
126 0
|
4月前
|
小程序 Java
【aspose-words】Aspose.Words for Java模板语法详细剖析
本文通过详细分析Aspose.Words for Java模板语法,介绍了使用条件块、变量和动态合并表格单元格三个常用模板标签,并结合实际案例进行演示。通过这三个标签的实操,帮助读者更好地掌握Aspose.Words的使用技巧。此外,还提供了官方文档链接以便进一步学习。
157 0
【aspose-words】Aspose.Words for Java模板语法详细剖析