前言
持续更新了
正文
问题来源
同学问我的一个问题。
题目
⼩明的抽屉⾥有n个游戏币，总⾯值m，游戏币的设置有1分的，2分的，5分的，10分的，⽽在⼩明所拥有的游戏币中有些⾯面值的游戏币可能没有，求⼀一共有多少种可能的游戏币组合⽅方式？
输⼊入：输⼊入两个数n(游戏币的个数)，m(总⾯面值)。
输出：请输出可能的组合⽅方式数；
我先想用动归来做，但是错了
var coins []int = []int{1, 2, 5, 10}
func countCoins(n, m int) int {
if n > m || m > 10*n {
return 0
}
dp := make([]int, m+1)
// init
for i := 0; i < len(coins) && coins[i] <= m; i++ {
dp[coins[i]] = 1
}
for i := 1; i < n; i++ {
for j := 0; j <= m; j++ {
if dp[j] == 0 {
continue
}
for k := 0; k < len(coins) && (j + coins[k] <= m); k++ {
dp[j+coins[k]]++
}
}
}
return dp[m]
}
算重复了 比如3个硬币，总共7块钱。
不能重复算
var coins []int = []int{1, 2, 5, 10}
func countCoins(n, m int) int {
res := 0
dfs(0, n, m, &res)
return res
}
func dfs(i, n, m int, res *int) {
if n < 0 || m < 0 {
return
}
if n == 0 && m == 0 {
(*res)++
return
}
for j := i; j < len(coins); j++ {
dfs(j, n-1, m-coins[j], res)
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
