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但是只能降到伪多项式级
相关阅读
Amazon research scientist refer星期一reference checked, 今天没有任何消息，还有戏吗？谁有EPI的pdf啊non compete 签还是不签 (转载)8年java开发求建议，到底去不去美国（华盛顿特区） (转载)找冬季的工作，何时集中投简历比较好？说说我的奇葩阿三同事第一个offer，不是太理想，如何选择javasctipt + REST 面试一般会问什么问题？ (转载)大家都是在什么网站下载C++, C#的电子书的？面试遇到自己准备过的题请教：移动APP的 服务端开发opening for fresh PHD or PHD drop out in quant major (转载)如果噢佛来了请问如果找国内BAT的码工的话上什么论坛比较好热门startup look for Data Scientist面试领英被拒总结复杂未生效h1b transfer。请帮助求意见～g家onsite分两次是好事么？我应该要求改成一天么？版主请进：公共账号