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 mainimport ( "fmt")const MAXN = 101const MAXM = 100001var val [MAXN]intvar cnt [MAXN]intvar dp [MAXM]boolvar n, m intfunc 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}

在这里插入图片描述