关于福大大架构师每日一题:20200224arr是面值数组其中的值都是正数且没有重复再给定一个正数aim每个值都认为是一种面值

福哥答案2020-02-24：
天然智慧即可。
1.递归。有代码。
2.动静布局。dp是二维数组。有代码。

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

package mainimport ("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代码
评论