2020-02-24: ARR is an array of values where the values are all positive and not duplicated. Let me give you a positive number, aim. Each value is considered a face value and the number of cards is considered infinite. Returns the minimum number of currencies that make up AIM

Natural wisdom can be. 1. The recursion. With the code. 2. Dynamic planning. Dp is a two-dimensional array. With the code.

The code is written in Golang, and the code is as follows:

package main

import (
"fmt"
)

func main(a) {
    arr := []int{1.2.3}
    aim := 8
    ret := minCoins1(arr, aim)
    fmt.Println(1. Recursion:, ret)
    ret = minCoins2(arr, aim)
    fmt.Println(2. Dynamic programming:, 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])
            ifnext ! = 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
    }
}
Copy the code

The result is as follows:

Left God Java code reviews