function fib(n){
if(n==1 || n==2) return 1
return fib(n-1) + fib(n-2)
}
function fib(n){
let memo = []
return helper(memo, n)
}
function helper(memo, n){
if(n==1 || n==2){
// 前两个
return 1
}
// 如果有缓存，直接返回
if (memo[n]) return memo[n];
// 没缓存
memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
return memo[n]
}
class Change{
constructor(changeType){
this.changeType = changeType
this.cache = {}
}
makeChange (amount) {
let min = []
if (!amount) {
return []
}
if (this.cache[amount]) { // 读缓存
return this.cache[amount]
}
for (let i = 0; i < this.changeType.length; i++) {
const leftAmount = amount - this.changeType[i]
let newMin
if (leftAmount >= 0) {
newMin = this.makeChange(leftAmount) // 这?句是动态规划的提现
}
if (leftAmount >= 0
&& (newMin.length < min.length - 1 || !min.length)) { // 如果存在更
?的找零硬币数, 则执?后?语句
min = [this.changeType[i]].concat(newMin)
}
}
return this.cache[amount] = min
}
}
const change = new Change([1, 5, 10, 20,50,100])
console.log(change.makeChange(2))
console.log(change.makeChange(5))
console.log(change.makeChange(13))
console.log(change.makeChange(35))
console.log(change.makeChange(135))
