a*n
2 楼
DP问题就是有记录中间最优解的brute-force，一般用数组、矩阵等等保存中间结果，
所以大部分是多项式复杂度。
所以大部分是多项式复杂度。
s*c
3 楼
经典的整数背包问题
dp但是只能降到伪多项式级
【在 M*******a 的大作中提到】
: 我老最近碰到一道，好像DP下来也指数级别了
dp但是只能降到伪多项式级
【在 M*******a 的大作中提到】
: 我老最近碰到一道，好像DP下来也指数级别了
M*a
4 楼
哦对的，还有subset sum也只是伪多项式
【在 s******c 的大作中提到】
: 经典的整数背包问题
: dp但是只能降到伪多项式级
【在 s******c 的大作中提到】
: 经典的整数背包问题
: dp但是只能降到伪多项式级
相关阅读
提供Juniper Networs 内推湾区很多烙印开的中介给介绍的工作机会靠谱吗？h1身份，上周被layoff,这周拿到offer，请问该怎么办？求问2个小公司：Machine Zone and Springpath.请问credit card collection strategist 面试怎么准备？dropbox再次贬值一分不值一道Google面试题，怎么做？（题目描述有误，已修改）放心 刷题是永远都不会改革的猥琐男干的？？工作中要小心作弊 (转载)大家有没有听说过TuneIn这个公司？现在剩下的实习空缺看似只招PhD了底层华人子弟参军是个好路 (转载)生物统计/统计的博士能找什么样的公司阿有在upwork上接活儿的吗？请教如何和说话不靠谱的HR打交道？50个评分最高的ceo.脸书黑人生命重要事件看工作AA (转载)记得之前谁说的signon bonus交flat tax rate？说英文：快而易懂的诀窍 (转载)