题目描述

假设有面额大小为 1，5，11的纸币，数量不限。
要求以尽量少的纸币数量，凑出给定大小 n的方案，给出最小纸币数量

eg: n 为 15，最少方案为 3个5，返回 3即可

解法

递归

/**
 * @param {int} n
 * @return {int} 
 * 
 */
function solution(n){
  if( n>=0 && n<5){
      return n
  }else if( n>=5 && n<11){
    const t = Math.floor(n/5)
    return n - t*5 + t
  }else{
    return Math.min(solution(n-1), solution(n-5), solution(n-11)) + 1
  }
}

穷举

/**
 * @param {int} n
 * @return {int} 
 * 
 */
function solution(n){
  const f = []
  f[0] = 0
  for(let i=1; i<=n; i++){
    let min = Infinity
    if(i-1>=0)
      min = Math.min(min, f[i-1]+1)
    if(i-5>=0)
      min = Math.min(min, f[i-5]+1)
    if(i-11>=0)
      min = Math.min(min, f[i-11]+1)
    f[i] = min
  }
  return f[n]
}

总结

• 求和为n的最少纸币数量，抽象为求f(n)
• 第一张纸币有三种选择
  • 选一张 1, 则 f(n) = f(n-1) + 1 (n >= 1 )
  • 选一张 5, 则 f(n) = f(n-5) + 1 (n >= 5)
  • 选一张 11, 则 f(n) = f(n-11) + 1 (n >= 11)
• 求 f(n)最小的问题，可以转化为求 Math.min(f(n-1), f(n-5), f(n-11))的问题
• 即 f(n)的值只和 f(n-1), f(n-5), f(n-11)有关系，很容易想到递归的解法
• 递归只关注特定数的值，逻辑清晰。既然如此，穷举出所有情况自然也可以, 即把f(0) - f(n)所有数都存下来，返回 f(n)即可