coin change

最简单的DP

package main
import "fmt"

func main() {
 //Enter your code here. Read input from STDIN. Print output to STDOUT
    var sum int
    var num int
    fmt.Scanln(&sum, &num)
    arr := make([]int, 0, num)
    for i := 0; i < num; i++ {
        var t int
        fmt.Scanf("%d", &t)
        arr = append(arr, t)
    }
    //var result int
    //recurit(arr, sum, &result)

    var dp = make([]int, sum+1)
    dp[0] = 1
    for i := 0; i < num; i++ {
        var coin = arr[i]
        for j := coin; j < len(dp); j++ {
            dp[j] += dp[j-coin]
        }
    }
    fmt.Println(dp[sum])
}