UVA 674_Coin Change
2024-08-25 02:19:36
题意:
给定一个数,求用1,5,10,25,50有多少种组合方式。
分析:
简单计数dp,dp[i][j]表示由前i+1个元素组成j的种数,注意dp[i][0]初始化为1,因为一个元素也不选的方法总是有一种。
代码:
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 7500;
long long dp[10][maxn + 5];
int main (void)
{
int a[5]={1,5,10,25,50};
int n;
memset(dp, 0, sizeof(dp));
for(int i = 0; i <=5; i++) dp[i][0] = 1;
for(int i = 0; i < 5; i++){
for(int j = 1; j < maxn; j++){
if(j-a[i]>=0){
dp[i+1][j] = dp[i][j]+dp[i+1][j-a[i]];
}else
dp[i+1][j] = dp[i][j];
}
}
while(cin>>n){
cout<<dp[5][n]<<endl;
}
}
最新文章
- Kinect开发随笔①——红外扫描仪(Kinect 数据源)
- Web API与文件操作
- 更新AD对象属性值
- [Arduino+Android] 自制土砲智能安全帽
- VS2010 Web项目需要缺少的Web组件才能加载
- 用Cython加速Python程序以及包装C程序简单测试
- [编程语言][java][java se]java泛型中? T K V E含义(学习)
- python之enumerate()函数的探究
- Connect2015 简要整理
- jmeter日记
- 面试题之-----String,StringBuffer,StringBuilder的区别
- Android 开发笔记___图像视图
- Libgdx1.6.2发布,跨平台游戏开发框架
- RocketMQ_问题_启动报错,修改堆内存大小
- 创建MySQL用户 赋予某指定库表的权限
- Jacobi-Anger expansion
- Linux I/O 调度器
- react 知识点2
- Jenkins使用简易教程
- PyCharm2018专业版激活步骤