如何判断一个问题是否可用动态规划算法求解？

如何判断一个问题是否可用动态规划算法求解？

这个就要凭经验了嘛。。

动态规划的题都是可以分出阶段的，比如背包问题可以由前i种物品的情况推导出前i+1种物品。

很多动态规划都是要求最优化某个值，有最优子结构性质，它的逻辑就是：要我求出前i+1种物品的最优值，我先求出前i种物品的最优值，然后再对第i+1个物品做决策。

也有统计类的DP，这时你就要思考如何划分阶段能够不重不漏。

一个问题有环状结构一般就不能用DP，比如求图的最短路。如果是链状结构就可以用DP，例如有向无环图的最短路。（其实把DP的状态关系画出来就是一个DAG）

还有嘛，熟练掌握treeDP，背包，各种区间、网格、线性DP，状态压缩，见到题就有思路了。

其实有时候题做不出来你可以专门想想是不是可以用DP做，f[i][j]，让i代表什么…j代表什么…

有很多奇怪的题也可以莫名其妙地用DP解决。这只能靠多做题和多思考了。。追问谢谢，回答的很仔细，能再举几个有环不能用DP的例子吗？我在网上看求最短路径貌似是可以用DP的，比如弗洛伊德算法追答floyd算法，其实也是把决策分成n个阶段，是以中间点来划分的，必须承认这是很巧妙的想法，不是常规思路。

找了找，带有环结构的题貌似不多，可能是因为一旦有环结构就难做，所以不出这种题。。不过仔细想想，网络流二分图匹配这样的图论问题都是因为有环所以不能用DP做，好在人们发明了许多算法来解决它们，高斯消元也是。。既然没法划分阶段，人们只能用一种全局性的眼光去解决，或者干脆用贪心瞎搞。。

对了，我说的“有环”其实就是有后效性，能用动态规划做必须满足两个性质：最优子结构（就是能划分阶段而且大问题的最优解可以由小问题推出来），无后效性（通俗的说就是没有环结构）

呃，其实这些理论对做题没什么大用，做题就是凭直觉。。

用搜索的方法会出现大量重复信息追问什么意思

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息