硬币问题 动态规划_动态规划

硬币问题 动态规划_动态规划动态规划-硬币问题分析

大家好,又见面了,我是你们的朋友全栈君。

什么是动态规划

上次对动态规划已经有了个大概的分析。引用维基百科的话就是:
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems

翻译过来就是动态规划就是通过拆分问题,来解决复杂的问题的一个方式。所以我们也知道,动态规划的核心就是如何取拆分这个问题那如何拆分问题,这个也就成为我们要去研究的重点。借鉴于大部分权威人士比较认同的观点是:拆分问题,靠的是状态的定义和状态转移方程的定义。
这里有一遍知乎是对上面的定义的见解:www.zhihu.com/question/23…

什么是状态的定义

我们对状态的定义是这样的:解答动态规划问题,需要开一个数组,数组中的每一个元素f[i]或f[i][j]代表了什么。而状态的定义需要两个步骤:
1.最后一步;
2.子问题。

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example Given coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Given coins = [2], amount = 3 return -1.

Notice You may assume that you have an infinite number of each kind of coin.

问题简单解释:现有不同币值的硬币,凑足一个给定的金额,不能多不能少,得出最少的硬币个数;如果无解,返回-1。

解题思路

那我们重新返回之前说的状态的定义的两个步骤。
最后一步:

我们就从例子里面说的,有1,2,5三个币值的硬币,凑足11块。我们假设最优策略是k个硬币凑足了11块,最后的一块硬币币值是a(K)元,则前面的硬币拼出的币值为11-a(K)元,这就是先着手最后一步的状态定义。
然后从子问题讲:
由于我们已经从最后一步定义,将原问题转化成另外一个问题是用最少的硬币凑足11-a(K)元,此时将原规模变小,而此时的问题就是原问题的子问题。可以将凑足多少元(即规模)定义为X,则可以用状态f(X) = 用最少的硬币凑足X元。我们假设最后一枚硬币是1,则f(11) = f(11 -1)+1枚;最后一枚是2,则f(11) = f(11-2)+1枚;同理,最后一枚为5,则f(11)=f(11-5)+1枚,即其实最少的硬币为f(11)=min{f(11-1)+1,f(11-2)+1,f(11-5)+1}。 我们可以用程序进行表示:

// 递归解法 
// 没有考虑边界问题
伪代码
int f(x){
if(x==0)return 0;
int res = Integer.MAX_VALUE;
if(x>=1){
res = Math.min(f(x-1)+1,res);
}
if(x>=2){
res = Math.min(f(x-2)+1,res);
}
if(x>=5){
res = Math.min(f(x-5)+1,res);
}
return res;
}
复制代码

但递归法解法做了很多重复计算,比如f(9)->f(11-1)->f(10-9)或者f(11-2)计算可得。这时候我们可以从动态规划第二部分—状态的转移。

其实很简单将f(x) 变成一个数组f[x],将计算结果保存起来。此时函数f[x]=min{f[x-1]+1,f[x-2]+1,f[x-5]+1}。
由于是个数组,所以我们应该考虑下边界和初始值的问题。假设拼不出来的值如f[-1]或者f[-3]这种,我们定义为正无穷Max_Value,初始值f[0]=0代表要拼出0元即为0个硬币。此时我们应当从小到大顺序算出每个元素的最小硬币值,即:
f[1]=min{f[1-1]+1,f[1-2]+1,f[1-5]+1}=f[0]+1 = 1

f[2] = min{f[2-1]+1,f[2-2]+1,f[2-5]+1} = f[0]+1 = 1,

我们不难发现,当f[2]以1块为最后的硬币时,f[1]其实已经保存该值的最小硬币数,不会重复计算,且算法时间度是X*3

可以看下程序:

public int coinChange(int[] a, int M) {
        // write your code here
        int length = a.length;
        int []f = new int[M+1];

        // 初始化
        f[0]=0;
        for(int i=1;i<=M;i++){
            // 先将f[i]初始无穷大,进行对比
            f[i]= Integer.MAX_VALUE;
            for (int j=0;j<length;j++){
                // 凑足的金额一定得大于硬币的值且减了硬币不应该等于无穷大
                if(i>=a[j]&&f[i-a[j]]!=Integer.MAX_VALUE&&f[i-a[j]]+1<f[i]){
                    f[i]= f[i-a[j]]+1;
                }
            }
        }
        if(f[M]==Integer.MAX_VALUE){
            return -1;
        }else {
            return f[M];
        }
    }
复制代码

作者简介

考拉后端开发小哥Rowland,热爱运动还有点萌!

转载于:https://juejin.im/post/5ce7d44351882530810dfd1d

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/106808.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 十二、Maven项目模板「建议收藏」

    十二、Maven项目模板「建议收藏」Maven提供用户,使用原型的概念,不同类型的项目模板(以数字614)是一个非常大的列表。Maven帮助用户快速开始使用以下命令创建新的Java项目mvnarchetype:generate什么是原型?原型是一个Maven插件,其任务是创建一个项目结构按照其模板。我们将使用快速启动原型插件在这里创建一个简单的Java应用程序。使用项目模板让我们打开命令控制

  • 不同宿主机docker 通信_如何设置同网段IP

    不同宿主机docker 通信_如何设置同网段IP依赖包net-toolsiproute2bridge-utilsgitcurl权限需要在root下执行脚本dnet.shj脚本内容#likebr0要创建的桥接设备名BRNAME=$1#likeeth0要矫健的网络接口名IFNAME=$2#192.168.1.2/24当前主机IPLOCALIP=$3#192.168.1.1当前主机…

  • 基于Apache的反向代理服务器

    基于Apache的反向代理服务器众所周知Apache是目前最优秀的HTTP服务器。实际上它不仅能当作服务器使用,也能够被用来架设代理服务器。本文就如何使用Apache架设HTTP代理服务器进行说明。本文将基于Win32版的Apache2.0.47进行说明。以前的Apache1.x版配置方法稍有不同,但这里不作说明。 首先是Apache的安装。从http://www.apache.org上下载Apache的安装

    2022年10月20日
  • Ribbon的负载均衡策略及原理[通俗易懂]

    Ribbon的负载均衡策略及原理[通俗易懂]LoadBalance负载均衡是用于解决一台机器(一个进程)无法解决所有请求而产生的一种算法。像nginx可以使用负载均衡分配流量,ribbon为客户端提供负载均衡,dubbo服务调用里的负载均衡等等,很多地方都使用到了负载均衡。使用负载均衡带来的好处很明显:当集群里的1台或者多台服务器down的时候,剩余的没有down的服务器可以保证服务的继续使用使用了更多的机器保证了机器的良性使用,不会由于…

    2022年10月13日
  • 常见android手机分辨率

    4:3VGA     640*480 (Video Graphics Array)QVGA  320*240 (Quarter VGA)HVGA  480*320 (Half-size VGA)SVGA  800*600 (Super VGA)5:3WVGA  800*480 (Wide VGA)16:9FWVGA 854*480 (Full Wide VGA)

  • python xml转excel_一个python 脚本将XML文件转换到excel

    python xml转excel_一个python 脚本将XML文件转换到excel需要下载一个module:xlwt,如下是sourcecodeimportxml.dom.minidomimportxlwtimportsyscol=0row=0defhandle_xml_report(xml_report,excel):problems=xml_report.getElementsByTagName(“problem”)handle_problems(p…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号