动态规划到底是不是一种算法呢？
时间：2023-10-19 05:42:01 | 来源：网站运营
时间：2023-10-19 05:42:01 来源：网站运营
动态规划到底是不是一种算法呢？：动态规划并不是一种算法，而是一种思想。
类似的，还有贪心。
我认为你看到的当成一种算法，应该说是当做一个考点。毕竟对于竞赛/考试来说，有明确的考纲还是比较重要的。
贪心并不是一种算法，只是一种用满足局部最优来达到全局最优(需要严格的证明)的思想。
动态规划是一种在搜索中通过合并相同的状态来减少不必要的时间/空间开支的思想。
举个例子，动态规划最经典的01背包问题，最原始的是回溯法暴力搜索，复杂度为O(2^n)，而我们可以注意到在搜索过程中，我们并不在意总价值为x的时候，到底用了哪些物品。甚至也不在意是用了1个物品还是2个物品。这时候我们就可以把总价值为x的所有状态合并成1个状态。从搜索树上来看，就是把若干个子树合并成一个节点。注意到这样的合并是非常有意义的，因为深度为l的子树的节点个数是2^l个。
另一个经典的例子是最长公共子序列，暴力搜索的复杂度是O(2^n*2^m)，但是我们其实并不在乎在第一个串的前i个字符和第二个串的前j个字符的最长公共子序列长度为k，是哪k个字符。因此这时候我们把只要能构成第一个串的前i个字符和第二个串的前j个字符的最长公共子序列长度为k的情况都合并了。
在线咨询
