题意:通过指定数量的不同面值零钱,问能凑出从1到m之间钱数的个数。解法:做这个题时,最初是使用的背包九讲中多重背包的二进制划分转化成01背包这个时间复杂度为O(V*∑log(n[i]))的方法来做,结果TLE了。 后来把问题看成完全背包问题的变种,利用数组标签的方法解决,复杂度为O(VN)。
posted on 2010-11-29 17:38 David Liu 阅读(122) 评论(0) 编辑 收藏 引用 所属分类: 动态规划
Powered by: C++博客 Copyright © David Liu