分而治之算法中和动态规划的区别 [英] Difference between Divide and Conquer Algo and Dynamic Programming

问题描述

分治法和动态规划算法之间的区别是什么？如何在这两个词有什么不同？我不明白它们之间的区别。

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms ? How are the two terms different ? I do not understand the difference between them.

请举一个简单的例子来说明这两者之间并在任何区别，他们似乎什么理由是相似的。

Please take a simple example to explain any difference between the two and on what ground they seem to be similar.

推荐答案

分而治之

分而治之的工作方式是将问题划分为子问题，递归征服每个子问题，并结合这些解决方案。

Divide and Conquer works by dividing the problem into sub-problems, conquer each sub-problem recursively and combine these solutions.

动态规划

动态规划是解决问题的重叠子问题的技术。每个子问题解决只有一次，每个子问题的结果被存储在表（通常实现为一个数组或哈希表）以备将来参考。这些子解决方案可用于获得原始溶液和存储所述子问题的解决方案的技术被称为记忆化

Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as an array or a hash table) for future references. These sub-solutions may be used to obtain the original solution and the technique of storing the sub-problem solutions is known as memoization.

您可能会想到 DP =递归+再利用

一个经典的例子来理解上的差异会看到这两个对获得的第n个Fibonacci数的方法。勾选此材料的麻省理工学院。

A classic example to understand the difference would be to see both these approaches towards obtaining the nth fibonacci number. Check this material from MIT.

修改

分而治之的办法的

Divide and Conquer approach

动态规划法的

Dynamic Programming Approach

这篇关于分而治之算法中和动态规划的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！