c++基础算法动态DP解决CoinChange问题

目录
  • 问题来源
  • 问题简述
  • 解决方案
  • 真正的DP
  • 补充——硬币不能重复使用
  • 补充2——不同顺序表示不同组合
  • 结束语

问题来源

这是Hackerrank上的一个比较有意思的问题,详见下面的链接:

https://www.hackerrank.com/challenges/ctci-coin-change

问题简述

给定m个不同面额的硬币,C={c0, c1, c2…cm-1},找到共有几种不同的组合可以使得数额为n的钱换成等额的硬币(每种硬币可以重复使用)。
比如:给定m=3,C={2,1,3},n=4,那么共有4种不同的组合可以换算硬币

{1,1,1,1}

{1,1,2}

{2,2}

{1,3}

解决方案

基本思路是从硬币(coins)的角度出发,考虑coins[0]仅使用1次的情况下有几种组合,coins[0]仅使用2次的情况下有几种组合,依次类推,直到 (n - coins[0] * 使用次数) < 0 则终止,而每个 (n - coins[0]) 下又可以递归 (n - coins[0] - coins[1]) 的情况,直到考虑完所有的硬币。
这样说可能还是没有说清楚,下面以m=3,C={1,2,3},n=4为例,用图来说明一下(建议结合程序一起看)。

图1:coin Change不完整递归图

上图没有画出完整的递归过程(有点麻烦~偷了个懒),不过把能得出结果的几条路径都描绘出来了。其中,recursion(money, index)中,money指的是还没有进行兑换的钱,index指的是要用哪个coin去兑换,比如这里的0指的是coins[0]=1,1指的是coins[1]=2,2指的是coins[2]=3,3是不存在的,这也是程序的终止条件之一。 注意到再递归的过程中有重叠子问题(我用紫色标注出了其中一个),这就可以用动态规划的思想来解决了,创建一块空间来存储已经算过的结果就可以了。 # 程序代码 好了,下面直接上程序了,结合图看好理解~

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
long long recursion(vector<int> &coins, int money, int index, unordered_map<string, int> &memo){
	//终止条件2个
    if (0 == money)
        return 1;
    if (index >= coins.size() || money < 0)
        return 0;
    string key = to_string(money) + " , " + to_string(index);
    //如果记录中有的话就直接返回就好了
    if (memo.find(key) != memo.end())
        return memo[key];
    long long res = 0;
    int remaining = money;
    while(remaining >= 0){
        res += recursion(coins, remaining, index + 1, memo);
        remaining -= coins[index];
    }
    //记录一下
    memo[key] = res;
    return res;
}

long long make_change(vector<int> coins, int money) {
	//用哈希表来记录 <剩下的钱-用的硬币>:换硬币的组合数
    unordered_map<string, int> memo;
    long long res = recursion(coins, money, 0, memo);
    return res;
}

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<int> coins(m);
    for(int coins_i = 0;coins_i < m;coins_i++){
       cin >> coins[coins_i];
    }
    cout << make_change(coins, n) << endl;
    return 0;
}

Sample Input

10 4
2 5 3 6

Sample Output

5

真正的DP

上面的那段代码是以自顶向下的方式来解决问题的,思路比较清晰,而真正的动态规划是自底向上的,思路其实也差不多,下面给出代码~

long long make_change(vector<int> coins, int money) {
    vector<long long> memo(money + 1, 0);
    memo[0] = 1;
    for (int i = 0; i < coins.size(); i++){
        for (int j = coins[i]; j <= money; j++){
            memo[j] += memo[j - coins[i]];
        }
    }
    return memo[money];
}

补充——硬币不能重复使用

如果每种硬币不能重复使用的话,又该怎么办呢?这只需要再程序上做一些小的改动就可以了,真的是非常神奇~
要细细体会一下~

long long make_change(vector<int> coins, int money) {
	vector<long long> memo(money + 1, 0);
	memo[0] = 1;
	for (int i = 0; i < coins.size(); i++){
		//改动处:由从前往后改成了从后往前,略去了重复的情况
		for (int j = money; j >= coins[i]; j--){
			memo[j] += memo[j - coins[i]];
		}
	}
	return memo[money];
}

补充2——不同顺序表示不同组合

然后再来变一变,如果每种硬币可以使用无限多次,但是不同的顺序表示不同的组合,那么又有多少种组合呢?
比如:

coins = [1, 2, 3]
money = 4

可能的组合情况有:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

注意,不同的顺序序列表示不同的组合~

所以结果是7。

这种情况下的代码是:

long long make_change(vector<int> coins, int money) {
	vector<long long> memo(money + 1, 0);
	memo[0] = 1;
	//改变了里外循环的顺序
	for (int i = 1; i <=money; i++){
		for (int j = 0; j < coins.size(); j++){
			if (i - coins[j] >= 0)
				memo[i] += memo[i - coins[j]];
		}
	}
	return memo[money];
}

要仔细体会一下三种情况下的区别和代码微妙的变化~

结束语

动态规划的代码量其实不大,但是思维量还是挺大的,要写正确还是要折腾挺久的~
本人是初学者,如有错误,还请指正~希望大家以后多多支持我们!

(0)

相关推荐

  • C语言动态规划之背包问题详解

    01背包问题 给定n种物品,和一个容量为C的背包,物品i的重量是w[i],其价值为v[i].问如何选择装入背包的物品,使得装入背包中的总价值最大?(面对每个武平,只能有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入物品多次) 声明一个数组f[n][c]的二维数组,f[i][j]表示在面对第i件物品,且背包容量为j时所能获得的最大价值. 根据题目要求进行打表查找相关的边界和规律 根据打表列写相关的状态转移方程 用程序实现状态转移方程 真题演练: 一个旅行者有一个最多能装M公斤的背

  • C++动态规划之最长公子序列实例

    本文实例讲述了C++动态规划之最长公子序列解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 求出两个字符串中的最长公子序列的长度. 输入: csblog belong 输出: max length = 4 实现代码: #include <stdio.h> #include <string.h> int arr[200][200]; /* 表示str1的前i位和str2的前j位的最长公子序列的长度 */ int main() { char str1[100],str2[10

  • c++动态规划经典算法

    目录 基本思想 重要分析问题方法 动态规划算法实例 1.台阶问题 2.从矩阵左上角走到右下角最短路径问题 3.最大子数组问题 4.最长公共子序列 基本思想 动态规划算法通常用于求解具有某种最优性质的问题.在这类问题中,可能会有许多可行解.每一个解都对应于一个值,我们希望找到具有最优值的解.动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解.与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的.若用分

  • C语言使用DP动态规划思想解最大K乘积与乘积最大问题

    最大K乘积问题 设I是一个n位十进制整数.如果将I划分为k段,则可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定的I和k,求出I的最大k乘积. 编程任务: 对于给定的I 和k,编程计算I 的最大k 乘积. 需求输入: 输入的第1 行中有2个正整数n和k.正整数n是序列的长度:正整数k是分割的段数.接下来的一行中是一个n位十进制整数.(n<=10) 需求输出: 计算出的最大k乘积. 解题思路:DP 设w(h,k) 表示: 从第1位到第K位所组成的十进制数,设m(i,j)

  • c++基础算法动态DP解决CoinChange问题

    目录 问题来源 问题简述 解决方案 真正的DP 补充--硬币不能重复使用 补充2--不同顺序表示不同组合 结束语 问题来源 这是Hackerrank上的一个比较有意思的问题,详见下面的链接: https://www.hackerrank.com/challenges/ctci-coin-change 问题简述 给定m个不同面额的硬币,C={c0, c1, c2-cm-1},找到共有几种不同的组合可以使得数额为n的钱换成等额的硬币(每种硬币可以重复使用). 比如:给定m=3,C={2,1,3},n

  • php四种基础算法代码实例

    php四种基础算法:冒泡,选择,插入和快速排序法许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣.作为一个初级phper,虽然很少接触到算法方面的东西 .但是对于冒泡排序,插入排序,选择排序,快速排序四种基本算法,我想还是要掌握的.下面是我按自己的理解,将四个方法分析一遍.需求:分别用 冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中 的值按照从小到的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序法

  • C语言的10大基础算法

    算法是一个程序和软件的灵魂,作为一名优秀的程序员,只有对一些基础的算法有着全面的掌握,才会在设计程序和编写代码的过程中显得得心应手.本文是近百个C语言算法系列的第二篇,包括了经典的Fibonacci数列.简易计算器.回文检查.质数检查等算法.也许他们能在你的毕业设计或者面试中派上用场. 1.计算Fibonacci数列 Fibonacci数列又称斐波那契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21. C语言实现的代码如下: /* Displaying Fibona

  • Python机器学习之Kmeans基础算法

    一.K-means基础算法简介 k-means算法是一种聚类算法,所谓聚类,即根据相似性原则,将具有较高相似度的数据对象划分至同一类簇,将具有较高相异度的数据对象划分至不同类簇.聚类与分类最大的区别在于,聚类过程为无监督过程,即待处理数据对象没有任何先验知识,而分类过程为有监督过程,即存在有先验知识的训练数据集. 二.算法过程 K-means中心思想:事先确定常数K,常数K意味着最终的聚类(或者叫簇)类别数,首先随机选定初始点为质心,并通过计算每一个样本与质心之间的相似度(这里为欧式距离),将样

  • Java基础之动态代理Cglib详解

    一.前言 经测试,jdk创建对象的速度远大于cglib,这是由于cglib创建对象时需要操作字节码.cglib执行速度略大于jdk,所以比较适合单例模式.另外由于CGLIB的大部分类是直接对Java字节码进行操作,这样生成的类会在Java的永久堆中.如果动态代理操作过多,容易造成永久堆满,触发OutOfMemory异常.spring默认使用jdk动态代理,如果类没有接口,则使用cglib. 二.服务 package proxy.cglib; /** * @Description: <br/>

  • C++基础算法基于哈希表的索引堆变形

    目录 问题来源 问题简述 问题分析 代码展示 问题来源 此题来自于Hackerrank中的QHEAP1问题,考查了对堆结构的充分理解.成功完成此题,对最大堆或者最小堆的基本操作实现就没什么太大问题了. 问题简述 实现一个最小堆,对3种类型的输入能给出正确的操作: "1 v" - 表示往堆中增加一个值为v的元素 "2 v" - 表示删去堆中值为v的元素 "3" - 表示打印出堆中最小的那个元素 注意:题目保证了要删的元素必然是在堆中的,并且在任何时

  • 计算机科学中32个常用的基础算法

    奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做的一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序: 1.A* 搜索算法--图形搜索算法,从给定起点到给定终点计算出路径.其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序.算法以得到

  • 详解Spring中实现接口动态的解决方法

    前言 本文主要给大家介绍的是关于Spring实现接口动态的相关内容,分享出来供大家参考学习,下面话不多说,来一起看看详细的介绍吧. 关于这个问题是因为领导最近跟我提了一个需求,是有关于实现类Mybatis的@Select.@Insert注解的功能.其是基于interface层面,不存在任何的接口实现类.因而在实现的过程中,首先要解决的是如何动态实现接口的实例化.其次是如何将使接口根据注解实现相应的功能. 声明 解决方案是基于Mybatis源码,进行二次开发实现. 解决方法 我们先来看看Mybat

  • JavaScript BASE64算法实现(完美解决中文乱码)

    JavaScript 的 BASE64 算法 var BASE64={ enKey: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/', deKey: new Array( -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -

  • 深度学习开源框架基础算法之傅立叶变换的概要介绍

    傅立叶变换时数字信号处理的重要方法之一,是法国数学家傅立叶在1807年在法国科学学会上发表的一篇文章中所提出的,在文章中使用了正弦函数描述温度分布,而且提出了一个著名的论断:任何连续性的周期信号都可以由一组适当的正弦曲线组合而成.而这个论断被当时审查论文的著名数学家拉格朗日所否定,拉格朗日认为正弦函数无法组合成一个个带有棱角的信号,但是从无限逼近的角度考虑,可以使用正弦函数来非常逼近期直到表示方法不存在明显差异,这篇论文最终在在拉格朗日死后15年之久才得以发表. 傅立叶变换的分类 根据信号是是周

随机推荐