Difference Between Divide and Conquer and Dynamic Programming

Divide and conquer:

建基於多項分支遞迴的一種很重要的演算法範式。字面上的解釋是「分而治之」,就是把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。

Dynamic programming:

通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

Difference between divide and conquer and dynamic programming:

Divide and conquer combines the solutions of the sub-problems to obtain the solution of the main problem while dynamic programming uses the result of the sub-problems to find the optimum solution of the main problem.

Divide and Conquer Example:

  • Binary search
  • Merge sort

Dynamic programming Example:

  • Fibonacci數列
  • Longest Common Subsequence
  • Floyd-Warshall Algorithm

Ref:

https://pediaa.com/what-is-the-difference-between-divide-and-conquer-and-dynamic-programming/

https://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92