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

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

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

什么是动态规划

上次对动态规划已经有了个大概的分析。引用维基百科的话就是:
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)


相关推荐

  • python中的缩进快捷键_取消首行缩进快捷键

    python中的缩进快捷键_取消首行缩进快捷键文章目录前言注意:IDLE开发环境对缩进量的设置前言和其它程序设计语言(如Java、C语言)采用大括号“{}”分隔代码块不同,Python采用代码缩进和冒号(:)来区分代码块之间的层次。在Python中,对于类定义、函数定义、流程控制语句、异常处理语句等,行尾的冒号和下一行的缩进,表示下一个代码块的开始,而缩进的结束则表示此代码块的结束。注意:Python中实现对代码的缩进,可以使用空格或者Tab键实现。但无论是手动敲空格,还是使用Tab键,通常情况下都是采用4个空

    2022年10月13日
  • django配置文件详解_django实时读取日志

    django配置文件详解_django实时读取日志前言django框架的日志通过python内置的logging模块实现的,既可以记录自定义的一些信息描述,也可以记录系统运行中的一些对象数据,还可以记录包括堆栈跟踪、错误代码之类的详细信息。log

  • django 验证码_rhino5授权验证失败

    django 验证码_rhino5授权验证失败验证和授权概述Django有一个内置的授权系统。他用来处理用户、分组、权限以及基于cookie的会话系统。Django的授权系统包括验证和授权两个部分。验证是验证这个用户是否是他声称的人(比如用户名

  • 初级程序员如何提升自己(程序员的成长之路)

    入职后如何快速成长到CTO入职后三个月试用期要做的事三法宝,处理同事关系核心两点,处理好领导关系每件事都是学习的机会主动加班,试用期加班是学习的好机会未通过试用期,如何应对?前三年需要学的技术工作后,千万不要停止学习项目经验如何累积?JAVA高级技术还需要学习哪些?架构师课程如何学习?工作中,快速学习新技术的捷径(重要的是形成体系,而不是钻到某个技术点)…

  • linux怎样测试tty,ttylinux 设置

    linux怎样测试tty,ttylinux 设置准备工具0.下载ttylinux系统。http://minimalinux.org/ttylinux/downloadX86.html(ttylinux-i686-11.1.iso.gz)(bootcd-i386-5.3.iso.gz)1.下载thttpd。(一)ttylinux安装(ttylinux-i686-11.1.iso)1.将ttylinux-i686-11.1.iso.gz解压t…

    2022年10月22日
  • 卸载软件包命令_查看rpm包是否安装

    卸载软件包命令_查看rpm包是否安装可以先用rpm-q’xxx’或者rpm-qf’xxx/bin/xxxx.xx’来查询一下所属的rpm包的名字。然后用rpm-e’xxxxxx’来删之。’xxx/bin/xxxx.xx’是一个包中任意的文件’xxxxxx’是查询得到的rpm包的名称    rpm-e的时候后面的文件名不用加版本号 安全地卸载RPM卸载软件包,并不是简单地将原来安

发表回复

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

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