动态规划算法(DP) JAVA 菜鸟理解

??不知道动态规划是啥,搜索到这篇动态规划算法(DP)
现在把java版的动态规划理解记录一下


题目描述



给你六种面额1、5、10、20、50、100元的纸币,假设每种币值的数量都足够多,编写程序求组成N员(N为0-10000的非负整数)的不同组合的个数。



输入描述:



输入为一个数字N,即需要拼凑的面额



输出描述:



输出也是一个数字,为组成N的组合个数。



首先一个先有一个DP表格的想法
单元格的值 为当前金额,用当前拥有货币的组合方法
比如那个加粗的 4 的意思是 用{1 5 10} 3种货币 有4种组合方式可以组合成10元


币种 金额12345678910
11111111111
51111222223
101111222224
201111222224
501111222224
1001111222224

//定义拥有的币种
int[] money = {1, 5, 10, 20, 50, 100};
//需要组成的金额
int n = 10;
//存储行的组合次数
int[] li = new int[n + 1];
//设定初始值
li[0] = 1;
//拿到当前拥有最大金额
for (int m : money) {
//遍历需要组合的金额
for (int i = 1; i <= n; i++) {
//如果当前金额可以组成
if (i >= m) {
// i-m =(当前金额-需要组合金额)
//li[i-m] = (当前金额-需要组合金额)组合的需要次数
//li[i] = 上一次的组合总次数 + (当前金额-需要组合金额)金额 组合的需要次数
//用加粗的4解释就是 4 = 3+1;
//3 = DP[5][10]
//1 = DP[5][0] li[0]默认为1
li[i] = li[i] + li[i - m];
}
}
}

完整版代码
跑两遍就很直观了


public class Main {
public static void main(String[] args) {
//定义拥有的币种
int[] money = {1, 5, 10, 20, 50, 100};
//需要组成的金额
int n = 10;
//存储行的组合次数
int[] li = new int[n + 1];
//设定初始值
li[0] = 1;
//输出X轴值 (需要合成的金额)
System.out.printf("%4d | ", 0);
for (int i = 1; i < n + 1; i++) {
System.out.printf("%4d", i);
}

//为了美观。。。。没有意义
System.out.println();
for (int i = 0; i < n + 2; i++) {
System.out.printf("%4s", "??");
}
System.out.println();

for (int m : money) {
//输出Y轴坐标轴值 (拥有金额)
System.out.printf("%4d | ", m);
for (int i = 1; i <= n; i++) {
if (i >= m) {
li[i] = li[i] + li[i - m];
}
}
sout(li);
}
}

//输出当前组合值
private static void sout(int[] li) {
for (int i = 1; i < li.length; i++) {
System.out.printf("%4d", li[i]);
}
System.out.println();
}
}

相关文档

  • 中职教学心得体会
  • sql server 2008 服务无法启动(报1053错误)
  • 在食品药监系统党风廉政建设工作会议上的讲话
  • 好看的微信头像图片大全
  • 商业土地租赁合同
  • 浙江省双一流大学名单
  • MySQL分页坑(limit+order by数据重复)
  • vue中 transition组件使用总结
  • 2017上学期幼儿园大班教学工作总结
  • 小组合作读书心得体会
  • 联想小新pro14/yoga 14s 2021安装ubuntu/kali/manjaro问题排雷,解决自带键盘、触摸板和显卡驱动问题
  • word里面表格线条颜色怎么改
  • 有关学科评估高校排名参考
  • 老师我想对您说说心里话作文
  • 竞业限制合同范本
  • 诱发肺纤维化的病因有哪些 诱发肺纤维化的病因
  • 山公园一日游
  • 高中下学期学习计划
  • 什么是盆腔积液
  • 初学JavaWeb-spring task的使用
  • 电脑黑屏开不了机怎么办
  • 感谢支持自己朋友的话
  • excel计数公式
  • 解析-366API如何解决微信中无法下载APP的问题
  • NeurIPS 2018 | 腾讯AI Lab参与提出构建非局部模块的新方法
  • 周漾?哥哥是谁叫什么名字周漾?哥哥王梓豪演过什么电视节目吗
  • 口袋饼
  • 2020年湖南邵阳市公务员报名已开通
  • 用java写出华为的代码_8 分钟写出代码(华为笔试题)
  • 橄榄球的起源介绍
  • 电脑版