求问动态规划和NP问题有何联系
很多一般化的问题如果是NP问题，但是加入一些限制条件就能变成P问题（比如每个输入或输出有确定的范围这种不起眼的限制条件）。但是这和动态规划（或者说具体算法）没什么关系。然后再赞同并纠正一下 @Xinran He 第一句不太严谨的说法：一个特定问题使用特定算法会有一个时间复杂度 ；这个问题本身也有一个时间复杂度，是定义为对其使用所有算法的时间复杂度的最小值。所以“更高效的解法”严格来说是针对于人们直观的暴力解法而言的，而不是对问题本身，因为问题的时间复杂度是确定的。更一般的来说，对于“任意”给定问题，我们没有办法确定它的时间复杂度，只能通过构造算法的方式来说这个问题的时间复杂度小于等于我们目前的算法（对于特殊问题，可以用特殊方法计算时间复杂度的理论下限就另当别论）。
■网友
动态规划本质上与穷举无异, 理论上可以应用于几乎所有可以用穷举来解决的优化问题但有没有效果,要看问题本身包含的重叠子问题的多寡: 如果有大量的重叠子问题,那么应用动态规划是明智的；否则,你懂的.
■网友
简言之很多NP-hard的问题都可以通过动态规划得到更高效的解法，但即使如此动态规划的运行时间仍旧不是polynomial的以旅行商问题（TSP）为例暴力枚举复杂度为O(n*n!) 用DP求解可以达到O(n^2 * 2^n)的复杂度
■网友
整数规划是NP难的，有动规算法，之间没什么关系不矛盾
■网友
many times the curse of dimensionality implies exponential complexity
推荐阅读
- 江苏■江苏交控坚持问题导向、瞄准职工需求——找准“病灶”当好“产改先行官”
- 贵州在建骨干水源工程达到465座有效解决工程性区域性缺水问题
- 四川眉山瓦屋山景区就游客投诉、停车难等问题公开道歉
- 杭州已整改城市道路无障碍环境问题12467处
- 互联网怎样解决“家政服务上门速度慢”的问题
- 中东问题|
- 中国网汽车|购车2个多月、仅行驶8000多公里 宝骏730遭遇7处问题
- |沛县深入开展教育领域突出问题专项整改
- 交换机，路由器经常性的死机咋办
- 微博目前已经支持文本，图片，位置分享，为啥没有语音和视频呢微博的pm肯定想过这两种微博形态，但迟迟不做的原因到底是啥。是语音和视频不符合产