Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
We are trying to count the number of distinct sets.
Since order does not matter, we will impose that our solutions (sets) are all sorted in non-decreasing order (Thus, we are looking at sorted-set solutions: collections).
For a particular and (now with the restriction that , our solutions can be constructed in non-decreasing order), the set of solutions for this problem, , can be partitioned into two sets:
- There are those sets that do not contain any and
- Those sets that contain at least 1
If a solution does not contain , then we can solve the subproblem of with , or the solutions of .
If a solution does contain , then we are using at least one , thus we are now solving the subproblem of , . This is .
Thus, we can formulate the following:
with the base cases:
- (one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0)
- (no solution -- negative sum of money)
- (no solution -- we have money, but no change available)
先上最优解:
public int coinChange(int[] S, int N) { int[] f = new int[N+1]; f[0] = 1; for(int i=0; i<S.length; i++) { for(int j=S[i]; j<=N; j++) { f[j] += f[j-S[i]]; } } return f[N]; }
Recursive Method:
// Returns the count of ways we can sum S[0...m-1] coins to get sum n int count( int S[], int m, int n ) { // If n is 0 then there is 1 solution (do not include any coin) if (n == 0) return 1; // If n is less than 0 then no solution exists if (n < 0) return 0; // If there are no coins and n is greater than 0, then no solution exist if (m <=0 && n >= 1) return 0; // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1] return count( S, m - 1, n ) + count( S, m, n-S[m-1] ); }
Dynamic Programming:
int count( int S[], int m, int n ) { int i, j, x, y; // We need n+1 rows as the table is consturcted in bottom up manner using // the base case 0 value case (n = 0) int table[n+1][m]; // Fill the enteries for 0 value case (n = 0) for (i=0; i<m; i++) table[0][i] = 1; // Fill rest of the table enteries in bottom up manner for (i = 1; i < n+1; i++) { for (j = 0; j < m; j++) { // Count of solutions including S[j] x = (i-S[j] >= 0)? table[i - S[j]][j]: 0; // Count of solutions excluding S[j] y = (j >= 1)? table[i][j-1]: 0; // total count table[i][j] = x + y; } } return table[n][m-1]; }
Time Complexity: O(mn)
Following is a simplified version of method 2. The auxiliary space required here is O(n) only.
int count( int S[], int m, int n ) { // table[i] will be storing the number of solutions for // value i. We need n+1 rows as the table is consturcted // in bottom up manner using the base case (n = 0) int table[n+1]; // Initialize all table values as 0 memset(table, 0, sizeof(table)); // Base case (If given value is 0) table[0] = 1; // Pick all coins one by one and update the table[] values // after the index greater than or equal to the value of the // picked coin for(int i=0; i<m; i++) for(int j=S[i]; j<=n; j++) table[j] += table[j-S[i]]; return table[n]; }
Reference:
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
相关推荐
飞歌G6IV刷机包,恢复出厂解决车机问题
无人机最强算法源码,易于部署和学习交流使用
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
无人机最强源码,无人机算法,易于部署和学习交流使用
数据来源:中国统计NJ-2023版
无人机最强算法源码,易于部署和学习交流使用
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
PP-OCR det
无人机最强算法源码,易于部署和学习交流使用
麦肯锡 营销 概述与基本框架gl.ppt
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
无人机最强源码,无人机算法,易于部署和学习交流使用
无人机最强源码,无人机算法,易于部署和学习交流使用
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Kendryte K210人工智能芯片应用程序集合,包括人脸检测、颜色检测、目标检测和分类、二维码和Apriltag代码检测以及和ArduPilot飞控软件的通信。这些应用程序已部署到无人机终端。This repository is a collection of appl….
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
PHP开源 trx自动兑换机器人源码,一款自动USDT兑换TRX的telegram机器人源代码,完美无措,简单部署,直接运营,无后门,无BUG,功能强大,带管理后台.zip
基于51单片机+lcd12864显示俄罗斯方块小游戏MCU软件源代码 * 单 片 机:STC89C52RC * 简 述:使用LCD12864显示的俄罗斯方块程序 * 功 能:计分,下一个方块预览,欢迎结束界面,长按连续左右移,暂停(按键Left+Turn) * IO口设定:按键 sbit key_sr_left=P3^7; sbit key_sr_turn=P3^6; sbit key_sr_right=P3^5; sbit key_sr_down=P3^4; LCD12864 sbit RS_Port=P1^0; sbit RW_Port=P1^1; sbit E_Port=P2^5; sbit PSB_Port=P1^2; sbit RST_Port=P1^4; 数码管锁存器 sbit dula=P2^6; sbit wela=P2^7;
企业数智化转型全攻略:新质生产力赋能数字化运营体系建设方案.pptx
数据来源:中国统计NJ-2023版