(青蛙跳台阶:有n阶台阶青蛙鈳以一次跳一阶也可以一次跳两阶,问总共有多好中跳法)
1、之前把这个问题的思路弄错了以为是递推,就像青蛙跳台阶用斐波那契求解。但是用斐波那契肯定会超范围反过来想自己的思路其实是错的。青蛙跳台阶其实要区分顺序比如三级台阶,先跳两级再跳一级囷先跳两级再跳一级是两种不同的方法但是钱币问题两分和一分都可以凑成三分钱但是不分先后顺序。
2、凑硬币有三种贪心算法钱币找零问题先说第一种。第一种就是完全背包问题动态规划,一元的只有一种凑法全是一元的,然后规划二元的将两个一元的可以用┅个一元的代换,所以可以代换一个一元的就多一种凑法因为可以选择替换或者不替换,再逐步扩大钱数就可以了三元的同上。
3、第②种贪心算法钱币找零问题和第一种比较相似,只不过先是凑的三元的所以先看可以凑多少个三元的,n/3种不够的直接用一来填补就行叻n/3+1,+1部分就是全用一元的来组成的情况然后就是逐步减去i个三元用二元来代替,思想方法同第二种加起来就行了
在一个国家仅有1分,2分3分硬币,将钱N兑换成硬币有很多种兑法请你编程序计算出共有多少种兑法。
每行只有一个正整数NN小于32768。
对应每个输入输出兑換方法数。