设有n种不同面值的硬币各硬币的面值存于数组T1n中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1n中。对任意钱数0≤m≤20001设计一个用最少硬币找钱m的方法。对于给定的1≤n≤10硬币面值数组T和可以使用的各种面值的硬币个数数组Coins以及钱数m0≤m≤20001计算找钱m的最少硬币数。输入数据第一行中只有1个整数给出n的值第2行起每行2个数分别是Tj和Coi

思路：

1. 定义一个数组dp[i]表示找i元钱需要的最少硬币数。

2. 初始化dp[0]=0，其他dp[i]=INF。

3. 对每个硬币面值T[j]，从T[j]开始遍历到m，更新dp[i]=min(dp[i],dp[i-T[j]]+1)，其中dp[i-T[j]]表示找i-T[j]元钱需要的最少硬币数，加1表示使用了一枚面值为T[j]的硬币。

4. 最后得到的dp[m]就是找m元钱需要的最少硬币数。

5. 注意：如果dp[m]仍然是INF，则表示无解，输出-1。

代码实现：