最簡(jiǎn)單的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])
}
