人民币换算

人民币换算 #

我们知道人民币有1、2、5、10、20、50、100这几种面值。现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。

分析 #

其实这道题目和计算美女主播直播间密码这个题目类似，都是涉及类似一种度量单位的转换。

最简单的想法是我们首先有个函数可以判断能都用给定面值表示出来，然后问题转化为有多少种面值表示组合，这个是不是又想起来计算输入表达式+-*的所有可能计算结果这个题目，就是算出所有可能组合。我们依然可以采用递归的思路。

Just Try #

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

参考答案 #

const base = [1,2,5,10,20,50,100]
// console.show(available([5,1], 6))
function getChange(n, index){
  if(n == 0||n ==1||index == 0){
    return 1;
  }
  if(n < 0|| index < 0){
    return 0;
  }
  return getChange(n-base[index],index)+ getChange(n,index-1);
}
function algorithm(n){
  if(n <= 0){
    return -1;
  }
  let index = 0;
  for(let i = base.length-1;i >= 0;i--){
    if(n >= base[i]){
      index = i;
      break;
    }
  }
  return getChange(n,index);
}
function main(...param) {
  console.show("参数：" + param, "结果：" + JSON.stringify(algorithm(param)))
  testPerformance(algorithm, param)
}
main(6);

复制代码，动手试一下：在线编程环境