2020-02-24：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认

福哥答案2020-02-24：
自然智慧即可。
1.递归。有代码。
2.动态规划。dp是二维数组。有代码。

代码用golang编写，代码如下：

package mainimport (\"fmt\")func main() {arr := []int{1, 2, 3}aim := 8ret := minCoins1(arr, aim)fmt.Println(\"1.递归：\", ret)ret = minCoins2(arr, aim)fmt.Println(\"2.动态规划：\", ret)}const INT_MAX = int(^uint(0) >> 1)func minCoins1(arr []int, aim int) int {return process1(arr, 0, aim)}func process1(arr []int, index int, rest int) int {if index == len(arr) {if rest == 0 {return 0} else {return INT_MAX}} else {ans := INT_MAXfor zhang := 0; zhang*arr[index] <= rest; zhang++ {next := process1(arr, index+1, rest-zhang*arr[index])if next != INT_MAX {if ans > zhang+next {ans = zhang + next}}}return ans}}func minCoins2(arr []int, aim int) int {if aim == 0 {return 0}N := len(arr)dp := make([][]int, N+1)for i := 0; i < N+1; i++ {dp[i] = make([]int, aim+1)}dp[0] = 0for j := 1; j <= aim; j++ {dp[j] = INT_MAX}for index := N - 1; index >= 0; index-- {for rest := 0; rest <= aim; rest++ {dp[index][rest] = dp[index+1][rest]if rest-arr[index] >= 0 && dp[index][rest-arr[index]] != INT_MAX {dp[index][rest] = getMin(dp[index][rest], dp[index][rest-arr[index]]+1)}}}return dp[0][aim]}func getMin(a int, b int) int {if a < b {return a} else {return b}}

执行结果如下：