2024-03-06：用 go 语言，每一种货币都给定面值 val[i]，和拥有的数量 cnt[i]，想知道目前拥有的货币，在钱数为 1、2、3...m 时，能找零成功的钱数有多少？也就是说当钱数的范围是 1~

作者：福大大架构师每日一题

2024-03-06
北京
本文字数：1423 字
阅读完需：约 5 分钟

2024-03-06：用 go 语言，每一种货币都给定面值 val[i]，和拥有的数量 cnt[i]，

想知道目前拥有的货币，在钱数为 1、2、3...m 时，能找零成功的钱数有多少？

也就是说当钱数的范围是 1~m，返回这个范围上有多少可以找零成功的钱数。

比如只有 3 元的货币，数量是 5 张，

m = 10。

那么在 1~10 范围上，只有钱数是 3、6、9 时，可以成功找零，

所以返回 3，表示有 3 种钱数可以找零成功。

答案 2024-03-06：

来自左程云。

灵捷3.5

大体步骤如下：

1.创建一个数组 val，存储每种货币的面值，数组 cnt 存储拥有的每种货币的数量。

2.使用动态规划，创建一个长度为 m+1 的 bool 数组 dp，dp[i]表示钱数 i 是否可以找零。

3.初始化 dp[0]为 true，因为钱数为 0 时不需要找零，即为成功找零。

4.遍历每种货币，根据面值和数量的不同情况分别处理找零的逻辑。

4.a.如果数量为 1，遍历更新 dp 数组，当 j >= val[i]时，如果 dp[j-val[i]]为 true，则说明钱数 j 可以成功找零。

4.b.如果数量大于 1 且面值*数量大于 m，遍历更新 dp 数组，当 j >= val[i]时，如果 dp[j-val[i]]为 true，则说明钱数 j 可以成功找零。

4.c.如果数量大于 1 且面值*数量小于等于 m，使用更复杂的逻辑更新 dp 数组，计算出钱数 j 成功找零的情况。

5.遍历 dp 数组，计算找零成功的钱数有多少。

6.返回钱数成功找零的总数量。

总的时间复杂度为 O(n*m)，其中 n 为货币种类数，m 为钱数范围。

总的额外空间复杂度为 O(m)，主要是 dp 数组的空间。

go 完整代码如下：

package main
import (  "fmt")
const MAXN = 101const MAXM = 100001
var val [MAXN]intvar cnt [MAXN]intvar dp [MAXM]boolvar n, m int
func main() {
  inputs := []int{3, 10,    1, 2, 4, 2, 1, 1,    2, 5,    1, 4, 2, 1,    0, 0}
  ii := 0  for ii < len(inputs) {    n = inputs[ii]    ii++    m = inputs[ii]    ii++
    if n != 0 || m != 0 {      for i := 1; i <= n; i++ {        val[i] = inputs[ii]        ii++      }      for i := 1; i <= n; i++ {        cnt[i] = inputs[ii]        ii++      }      ans := compute()      fmt.Println(ans)    } else {      break    }  }}
func compute() int {  for i := 1; i <= m; i++ {    dp[i] = false  }  dp[0] = true
  for i := 1; i <= n; i++ {    if cnt[i] == 1 {      for j := m; j >= val[i]; j-- {        if dp[j-val[i]] {          dp[j] = true        }      }    } else if val[i]*cnt[i] > m {      for j := val[i]; j <= m; j++ {        if dp[j-val[i]] {          dp[j] = true        }      }    } else {      for mod := 0; mod < val[i]; mod++ {        trueCnt := 0        for j, size := m-mod, 0; j >= 0 && size <= cnt[i]; j -= val[i] {          trueCnt += boolToInt(dp[j])          size++        }        for j, l := m-mod, m-mod-val[i]*(cnt[i]+1); j >= 1; j -= val[i] {          if dp[j] {            trueCnt--          } else {            if trueCnt != 0 {              dp[j] = true            }          }          if l >= 0 {            trueCnt += boolToInt(dp[l])          }          l -= val[i]        }      }    }  }  ans := 0  for i := 1; i <= m; i++ {    if dp[i] {      ans++    }  }  return ans}
func boolToInt(b bool) int {  if b {    return 1  }  return 0}