贪心法和动态规划法的核心区别是什么
贪心法和动态规划法在解决问题时的思路和策略有着明显的不同，主要体现在以下几个方面：
-
核心思想
贪心法就是那种“当下最优”的策略，简单来说就是每一步都做出当前看来最好的选择，不管未来会不会出问题。有时候它真的能得到全局最优解，但更多时候只能得到局部最优解或者是一个比较接近的结果。
动态规划则不一样，它会把大问题拆成一个个小问题，逐步解决这些小问题，然后把答案“存起来”，避免重复计算，最终组合成整个问题的最优解。这个方法比较聪明，尤其适合那些“重叠子问题”和“最优子结构”明显的问题。 -
决策方式
贪心法在每一步都只考虑当前状态的最优选择，不回头看以前的选择，也不预判未来的结果。
动态规划则是全面考虑所有可能的选择路径，利用之前计算过的结果，综合判断，保证最终得到的解是全局最优。 -
适用场景
贪心法适合那些每一步的局部最优能导出全局最优的问题，比如找零钱、活动选择等。
动态规划适合问题有重叠子问题，且整体问题的最优解包含子问题最优解的情况，比如斐波那契数列、背包问题、最长公共子序列等。
动态规划的基本概念和常见套路有哪些
说到动态规划，咱们得先了解它的三要素和套路，弄明白这些，做题的时候就能事半功倍啦！
- 动态规划三要素
- 阶段：把问题拆成若干个阶段，每个阶段代表问题的一个步骤。
- 状态：每个阶段的状态代表问题在该阶段的具体情况。
-
决策：在每个阶段做出决策，决定下一步怎么走。
-
重叠子问题
动态规划的最大亮点是“重叠子问题”，也就是说，很多子问题会被重复计算。举个例子，计算斐波那契数列时，fib(5)会用到fib(4)和fib(3)，而fib(4)又会用到fib(3)，所以fib(3)被算了好多次。动态规划就是把这些结果存起来，别重复算了，节省时间！ -
最优子结构
这个很重要，就是说大问题的最优解可以由子问题的最优解组合而成。动态规划正是利用这个性质，逐步求解出全局最优解。 -
常见套路
- 线性DP：状态按顺序排列，比如最长递增子序列。
- 区间DP：状态对区间进行定义，比如矩阵链乘法。
- 背包DP：根据容量和物品选择状态转移。
- 树形DP：针对树结构的DP问题。
相关问题解答
-
贪心算法什么时候能保证得到全局最优解?
哎，这个嘛，贪心算法能保证全局最优解的情况其实不算多，但如果问题满足“贪心选择性质”和“最优子结构”，比如找零钱问题，贪心就稳得很！简单来说，就是每一步局部最优加起来就是全局最优，没啥坑爹的地方。 -
动态规划为什么要用“备忘录”或者“状态表”？
说白了，就是为了不重复计算，节省时间啊！举个例子，算斐波那契数列，没备忘录你会一直算同样的数字，浪费时间。备忘录就像个小抄，记录以前算过的结果，下一次直接拿来用，快得不要不要的。 -
贪心算法和动态规划哪个更好用？
这真得看你要解决的问题啦！贪心算法简单快捷，写代码也轻松，但不一定靠谱；动态规划复杂一点，代码写起来费劲，但结果稳妥靠谱。要是想简单快解决问题，贪心试试；要是想搞定复杂优化问题，动态规划必备。 -
动态规划的时间复杂度一般是多少？
这个嘛，动态规划的时间复杂度主要看状态数和状态转移复杂度。通常情况下，是多项式时间，比如O(n^2)或者O(n^3)，远比暴力递归快爆了。虽然写代码复杂点，但效率杠杠的，特别适合大规模问题。
发表评论