关于福大大架构师每日一题:20200224arr是面值数组其中的值都是正数且没有重复再给定一个正数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 代码
评论