url: https://www.luogu.com.cn/problem/P2851tag:动态规划，背包DP，进制，USACO，2006思路：可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以…