拼凑硬币问题

拼凑,硬币,问题 · 浏览次数 : 313

小编点评

```java public static long moneyWays(int[] many, int[] one, int money) { if (money < 0) { return 0; } if ((many == null || many.length == 0) && (one == null || one.length == 0)) { return money == 0 ? 1 : 0; } long[][] dpMany = many(many, money); long[][] dpOne = one(one, money); if (dpMany == null) { return dpOne[dpOne.length - 1][money]; } if (dpOne == null) { return dpMany[dpMany.length - 1][money]; } long res = 0; for (int i = 0; i < money; i++) { res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i]; res %= MOD; } return res; } ``` ```排版算法和数据结构笔记。归纳总结以上内容，生成内容时需要带简单的排版``` **排版算法** * 排版算法是一种将数据结构排版成特定顺序的算法。 * 排版算法可以帮助我们提高算法效率。 * 排版算法可以帮助我们降低时间复杂性。 **数据结构** * 数据结构是一种用于存储数据的算法。 * 数据结构可以帮助我们提高算法效率。 * 数据结构可以帮助我们降低时间复杂性。 **总结** * 排版算法和数据结构笔记是帮助我们提高算法效率的重要工具。 * 排版算法和数据结构笔记可以帮助我们降低时间复杂性。 * 排版算法和数据结构笔记可以帮助我们存储数据的算法。

正文

拼凑硬币问题

作者：Grey

原文地址：

博客园：拼凑硬币问题

CSDN：拼凑硬币问题

问题描述

现有 n1 + n2 种面值的硬币，其中前 n1 种为普通币，可以取任意枚，后 n2 种为纪念币， 每种最多只能取一枚（可能有重复值），每种硬币有一个面值，问能用多少种方法拼出 m 的面值?

题目链接见：牛客-拼凑硬币

主要思路

如果都用普通币，组合出 m 有多少种方法？假设得到 x 种方法。

如果都用纪念币，组合出 m 有多少种方法？假设得到 y 种方法。

如果是普通币 + 纪念币，组合出 m 有多少种方法？ 假设得到 z 种方法。

则 x + y + z 就是结果。

所以需要定义两个递归函数。

第一个递归函数：用纪念币，组成不同钱数的组合数量有多少

long[][] one(int[] arr, int money)

递归含义表示：用纪念币，返回组成不同钱数的组合数量有多少。由于纪念币每种最多只能选一个，所以这是一个经典的背包问题。

注：这个递归返回的是一个二维数组 dp，dp[i][j]表示 0 号到 i 号纪念币任意选择的情况下，组合出 m 有多少种方法。

递归含义确定后，二维数组 dp 的第 0 列的值已经可以很快确定，因为 dp[i][0] 表示 0 号到 i 号纪念币任意选择的情况下，组成 0 面值有多少方法。

显然只有一种方法，就是什么都不选，即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}

dp[0][arr[0]] 的值也可以确定，因为 dp[0][arr[0]] 表示：0 号面值的纪念币，如何组成arr[0] 的面值，显然只有一种方法，就是选 0 号的面值，但是需要满足一个条件，即 arr[0] <= money，即

if (arr[0] <= money) {
    dp[0][arr[0]] = 1;
}

接下来就是普遍情况，对于任意 dp[i][j] 来说，首先可以有一种决策，不要 i 位置的纪念币，即

dp[i][j] = dp[i-1][j]

第二种决策，就是使用 i 位置的一枚纪念币，此时，要满足前提条件，即 arr[i] 位置的面值不能超过剩余面值

即：

dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;

递归函数的完整代码如下

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

第二个递归函数：用普通币，组成不同钱数的组合数量有多少

long[][] many(int[] arr, int money)

递归含义表示：用普通币，组成不同钱数的组合数量有多少。也是返回一个二维数组 dp，dp[i][j]表示 0 号到 i 号普通币任意选择的情况下，组合出 m 有多少种方法。

根据递归含义，二维数组 dp 的第 0 列的值全为 1， 组成 0 面值的组合只有一种情况，就是用 0 枚普通币。即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}

第 0 行也比较好确认，就是枚举 arr[0] 最多可以使用多少枚，即

for (int j = 1; arr[0] * j <= money; j++) {
    dp[0][arr[0] * j] = 1;
}

接下来是普遍位置，dp[i][j] 有两个决策，第一个决策，不使用 i 位置的普通币，即

dp[i][j] = dp[i-1][j]

第二个决策，使用 i 位置的普通币，此时，要满足前提条件，即 arr[i] 位置的面值不能超过剩余面值
即：

dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;

所以，递归函数的完整代码如下

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

整合函数，普通币和纪念币一起使用

有了上述两个 dp ，就可以很方便计算两种硬币一起使用过程的组合数量，核心思路就是这句

dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];

即：只用 普通币完成 i 面值的组合数量是 M，用纪念币完成 money - i 面值的组合数量是 N，则 M * N 就是两者一起用组合成 money 面值的组合数量。

这个整合函数的完整代码如下


    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }

完整代码

import java.util.Scanner;

public class Main {
    static int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n1 = in.nextInt();
        int n2 = in.nextInt();
        int target = in.nextInt();
        int[] many = new int[n1];
        int[] one = new int[n2];
        for (int i = 0; i < n1; i++) {
            many[i] = Integer.parseInt(in.next());
        }
        for (int i = 0; i < n2; i++) {
            one[i] = Integer.parseInt(in.next());
        }
        System.out.println(moneyWays(many, one, target));
        in.close();
    }

    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }
}

更多

算法和数据结构笔记

拼凑 硬币 问题

与拼凑硬币问题相似的内容：

拼凑硬币问题

拼凑硬币问题 作者：Grey 原文地址： 博客园：拼凑硬币问题 CSDN：拼凑硬币问题 问题描述 现有 n1 + n2 种面值的硬币，其中前 n1 种为普通币，可以取任意枚，后 n2 种为纪念币， 每种最多只能取一枚（可能有重复值），每种硬币有一个面值，问能用多少种方法拼出 m 的面值? 题目链接见

拼凑 硬币 问题
313
以开发之名|线上家装新美学——梦想之家，由你来定

何谓家装？过去，人们辗转于各大家装城，购买时下流行的家具装饰，参考各类“过来人”和设计师的意见，糅杂一些样板间风格，依靠想象拼凑一个设计方案。而今天，在年轻一代的消费群体心中，家装的意义正发生深刻改变：要自由定义，坚决悦己，实用与美观兼得；要猫与鱼，花与叶，喜欢的音乐，收藏的手办都有自己的天地；要一

开发 家装 美学 梦想
179
Dlang 与 C 语言交互（二）

# Dlang 与 C 语言交互（二） > 随着需求不断增加，发现好像需要更多的东西了。在官网上找不到资料，四处拼凑才有了本文的分享。 上一文（[DLang 与 C 语言交互（一） - jeefy - 博客园](https://www.cnblogs.com/jeefy/p/17501476.htm

dlang 语言 交互
91
拼多多面试：Netty如何解决粘包问题？

粘包和拆包问题也叫做粘包和半包问题，它是指在数据传输时，接收方未能正常读取到一条完整数据的情况（只读取了部分数据，或多读取到了另一条数据的情况）就叫做粘包或拆包问题。 从严格意义上来说，粘包问题和拆包问题属于两个不同的问题，接下来我们分别来看。 1.粘包问题 粘包问题是指在网络通信中，发送方连续发送

netty
0
贴纸拼词问题

贴纸拼词问题 作者：Grey 原文地址: 博客园：贴纸拼词问题 CSDN：贴纸拼词问题 题目描述 有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。以多次使用每个贴纸，每个贴纸的数量是无限的。 返回你需要拼

贴纸 问题
44
Java 把多个音频拼接成一个

本文简要介绍了Java 把多个音频拼接成一个音频的方法，给出了一个基于JLayer（用于MP3）和TarsosDSP（一个音频处理库）的简化示例，并给出了详细的代码示例。

java
0
还在拼冗长的WhereIf吗？100行代码解放这个操作

通常我们在做一些数据过滤的操作的时候，经常需要做一些判断再进行是否要对其进行条件过滤。 普通做法 最原始的做法我们是先通过If()判断是否需要进行数据过滤，然后再对数据源使用Where来过滤数据。 示例如下： if(!string.IsNullOrWhiteSpace(str)) { query =

whereif
0
MySQL 字段截取拼接

@目录前言需求：拼接函数：截取函数：总结 前言 请各大网友尊重本人原创知识分享，谨记本人博客：南国以南i、 提示：以下是本篇文章正文内容，下面案例可供参考 需求： 将数据库中的某一个字段的前6位替换成一个新的字符串，其它位置不变。 拼接函数： CONCAT(A,B)：将A和B拼接起来。 截取函数：

mysql
0
贪心算法--拼接最大数字问题

博客地址：https://www.cnblogs.com/zylyehuo/ # -*- coding: utf-8 -*- from functools import cmp_to_key def xy_cmp(x, y): if x + y < y + x: return 1 # 表示 x>y

贪心 算法 拼接 最大
6
Python ArcPy批量拼接长时间序列栅格图像

本文介绍基于Python中ArcPy模块，对大量不同时相的栅格遥感影像按照其成像时间依次执行批量拼接的方法~

python arcpy 批量 拼接
186
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.