[DP]硬币问题
2024-10-11 02:15:27
今天再写一下硬币问题 为什么是再呢
这是个很羞耻的话题 昨天写了一遍硬币
在某谷上跑 没错 挂掉了 TLE MD_SB
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
有很多人说硬币问题是贪心去做
如果你遇到的测试点不呢么毒瘤
例1: 硬币的面值是 1 5 10 要凑出15元 min（硬币个数）
解1：（贪心）每次选最大 min=2
显然是可以得到正确答案的
但是如果硬币的面值是
例2：硬币的面值是 1 5 11 要凑出15元 min（硬币个数）
解2：（贪心）每次选最大 min=5
显然这是错误的 min应该等于3 三个五元
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
所以说 以后我们看到硬币问题的时候
一定不要再深陷于贪心 要多考虑几组测试数据
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DP常规思路：1、设计状态 f(n)为n元需要的最少硬币数
2、写状态转移方程
f(n)= min(f(n-1),f(n-5),f(n-11))+1
但是这题我们要注意一下 不能直接把状态转移方程带入
因为如果n=4 呢n-5，n-11是不是小于零啊
这时候我们加一个中间变量和判断就ojbk了
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
现在我们代码实现一下：
- #include<iostream>
- #include<cstdio>
- #define N 2333333
- using namespace std;
- int dp[100010],cost,m;
- int min(int x,int y){
- return x>=y?y:x;
- }
- int main(){
- scanf("%d",&m);
- cost=N;
- dp[0]=0;
- for(int i=1;i<=m;i++)
- {
- dp[i]=N;
- if(i-1 >= 0) dp[i]=min(dp[i],dp[i-1]+1);
- if(i-5 >= 0) dp[i]=min(dp[i],dp[i-5]+1);
- if(i-11 >= 0) dp[i]=min(dp[i],dp[i-11]+1);
- printf("dp[%d] =%d\n",i,dp[i]);
- }
- 月5日 10:56
- return 0;
- }
最新文章
- adb opendir failed ,permission denied
- Windows server 2008 R2充当路由器实现网络的互联(转)
- osgEarth例子
- DATEADD(Day, DATEDIFF(Day,0,ShippingTime), 0)
- java懒汉式单例遇到多线程
- matlab实现高斯牛顿法、Levenberg–Marquardt方法
- leetcode面试准备:Container With Most Water
- struts2 404处理
- QT第二天学习
- Vue中之nextTick函数源码分析
- 关于java线程中stop interrupt daemon wait notify
- Nginx服务器的图片防盗链
- thread run 和 start 的区别
- hdu 1754解题报告 (代码+注释)
- Constructing Roads----poj2421（最小生成树Kruskal）
- 解决input标签placeholder属性浏览器兼容性问题的一种方法
- python模块-json、pickle、shelve
- 在vue项目中使用swiper2.7.6
- 专家PID控制
- 20165230 2017-2018-2 《Java程序设计》第5周学习总结