DP解法的题目是不是肯定是多项式的？ - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - DP解法的题目是不是肯定是多项式的？

相关主题
● 关于n个数的所有和的一个问题	● 问一道google面试题(from careercup)
● 请教最优算法：最多装满水的桶？	● 谁给个不是brute force的解法
● Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？ (转载)	● 问个关于set的题
● Amazon interview question.(3)	● 问道题正方体八顶点
● split a string into words in a dictionary这题有最坏情况比exponential 快的解法么？	● 问一道G家经典老题
● 01 Knapsack brute force code	● PIE题: Phone number to words iterative 解法
● 求助一道FB的高频题non-overlap jobs	● bb家电面
● Amazon面筋	● 经典递归题需要搞懂非递归算法吗？

相关话题的讨论汇总
话题: dp话题: 多项式话题: 解法

进入JobHunting版参与讨论

1

(共1页)

M*******a 发帖数: 1633	1 我老最近碰到一道，好像DP下来也指数级别了
a***n 发帖数: 623	2 DP问题就是有记录中间最优解的brute-force，一般用数组、矩阵等等保存中间结果，所以大部分是多项式复杂度。
s******c 发帖数: 1920	3 经典的整数背包问题 dp但是只能降到伪多项式级【在 M*******a 的大作中提到】 : 我老最近碰到一道，好像DP下来也指数级别了
M*******a 发帖数: 1633	4 哦对的，还有subset sum也只是伪多项式【在 s******c 的大作中提到】 : 经典的整数背包问题 : dp但是只能降到伪多项式级

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 经典递归题需要搞懂非递归算法吗？	● split a string into words in a dictionary这题有最坏情况比exponential 快的解法么？
● 请问一个java的问题(leetcode subsets一题）	● 01 Knapsack brute force code
● 你们leetcode都刷到啥程度才敢去面FLG	● 求助一道FB的高频题non-overlap jobs
● Substring with Concatenation of All Words 还有更简洁的解法吗？	● Amazon面筋
● 关于n个数的所有和的一个问题	● 问一道google面试题(from careercup)
● 请教最优算法：最多装满水的桶？	● 谁给个不是brute force的解法
● Google面试怎么这么难啊，LG很难过，我该怎么劝他呢？ (转载)	● 问个关于set的题
● Amazon interview question.(3)	● 问道题正方体八顶点

相关话题的讨论汇总
话题: dp话题: 多项式话题: 解法

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)