Iterative DP solution - golang - 19ms


  • 0
    B
    func cChange(coins []int, amount int, seen []int) int {
        if amount <= 0 {
            return 0
        }
        for i := 1; i <= amount; i++ { 
            min := 4111111111
            for _, coin := range coins {
                res := -1
                if i >= coin  {
                    res = seen[i-coin] + 1
                    if res < min {
                        min = res
                    }
                }
            }   
            seen[i] = min
        }
        if seen[amount] == 4111111111 {
            return -1
        }
    
        return seen[amount]
    }
    
    func coinChange(coins []int, amount int) int {
        return cChange(coins, amount, make([]int, amount+1))
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.