leetcode322.零钱兑换

leetcode322.零钱兑换

基本思路

回溯算法的应用

1.循环（金额减去银币面额，银币）

2.凑不齐面额的忽略，能凑齐面额的组合取银币数最少的

3.重复执行1，2步骤，所有组合都被触发。别忘了用备忘录减少不必要的重复极损

解法代码

func coinChange(coins []int, amount int) int {
    memo:=make([]int,amount+1)
    for k,_:=range memo{
        memo[k]=666
    }
    return dp(coins,amount,memo)
}

func dp(coins []int,amount int, memo []int) int{
   
    if amount==0{
        return 0
    }

    if amount< 0{
        return -1
    }
     if memo[amount]!=666{
        return memo[amount]
    }

    res:=math.MaxInt

     for _, v:=range coins{
        sub:=dp(coins,amount-v,memo)
        if sub==-1{
            continue
        }
        res=min(res,sub+1)
     }
     if  res==math.MaxInt{
         memo[amount]=-1
     }else{
         memo[amount]=res
     }

     return memo[amount]
}

func min (x,y int) int{
    if x>y{
        return y
    }
    return x
}