前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动态规划入门_钱币兑换问题

动态规划入门_钱币兑换问题

作者头像
梅花
发布2020-09-28 10:34:42
1.3K0
发布2020-09-28 10:34:42
举报
文章被收录于专栏:梅花的学习记录

首先递推公式 : 钱币面值 从 1,一直遍历到 n , 然后兑换的面值从 j=1 到 j 等于最大的面值, 面对 第 i种面值的硬币,有两种选择,不选则当前硬币面值的所有情况 加上选择当前面值的

所有情况 ,于是 就得出了 一个 递推公式 F[ j ] += F[ j - value[ i ] ];

问题描述:

Problem Description 在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input 每行只有一个正整数N,N小于32768。

Output 对应每个输入,输出兑换方法数。

Sample Input 2934 12553

Sample Output 718831 13137761

Java 实现Ac 代码

代码语言:javascript
复制
 1 import java.util.Scanner;
 2 
 3 public class Main {
 4     
 5     public static void main(String[] args) {
 6         
 7         Scanner cin = new Scanner (System.in);
 8         while(cin.hasNext()){
 9             int n = cin.nextInt();
10             int [] value = {1,2,3};
11             int [] dp = new int [32800];
12             
13             dp [0] =1;
14             for(int i = 0;i<value.length;i++){
15                 for(int j = value[i];j<=n;j++){
16                     dp[j] = dp[j]+dp[j-value[i]];
17                 }
18             }
19             
20             
21             System.out.println(dp[n]);
22         }
23         
24     }
25 
26 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-04-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档