2020-02-24：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数。

福哥答案2020-02-24：

自然智慧即可。

1.递归。有代码。

2.动态规划。dp是二维数组。有代码。

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

package main

import (

"fmt"

)

func main() {

    arr := []int{1, 2, 3}

    aim := 8

    ret := 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_MAX

        for 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[N][0] = 0

    for j := 1; j <= aim; j++ {

        dp[N][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

    }

}

执行结果如下：

---

左神java代码

评论

2020-02-24：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数。的相关教程结束。