题解 | 换钱的最少货币数

package main

import (
    "fmt"
)

func main() {
    num, target := 0, 0
    for {
        n, _ := fmt.Scan(&num, &target)
        if n == 0 {
            break
        } else {
            coins := make([]int, num)
            for i:=0; i<len(coins); i++ {
                fmt.Scan(&coins[i])
            }
            dp := make([][]int, len(coins)+1)
            for i:=0; i<len(dp); i++ {
                dp[i] = make([]int, target+1)
                 if i==len(dp)-1 {
                    for j:=1; j<len(dp[i]); j++ {
                        dp[i][j] = -1
                    }
                }
            }
            for i:=len(dp)-2; i>=0 ; i-- {
                for j:=1; j <len(dp[i]); j++ {
                    dp[i][j] = dp[i+1][j]
                    if j>= coins[i] {
                        if dp[i][j-coins[i]] >= 0 {
                            if dp[i][j] == -1 {
                                dp[i][j] = dp[i][j-coins[i]] + 1
                            } else {
                                dp[i][j] = min(dp[i][j], dp[i][j-coins[i]] + 1)
                            }
                        } 
                    }
                }
            }
            fmt.Println(dp[0][target])
        }
    }
}

// func process(target int, coins []int, i int) int{
//     if target == 0 {
//         return 0
//     }
//     if i == len(coins) {
//         return -1
//     }
//     sum := target+1
//     for k:=0; k*coins[i] <= target; k++ {
//         sum1 := process(target-k*coins[i], coins , i+1)
//         if sum1 == -1 {
//             continue
//         }
//         sum = min(sum1+k, sum)
//     }
//     if sum == target+1 {
//         return -1
//     }
//     return sum
// }
func min(a, b int) int {
    if a<b {
        return a
    }
    return b
}