Dynamic Programming vs Divide-and-Conquer
Tags: javascript, algorithms, webdev, computerscience
Published: 2018-06-15 04:58:01

---
title: Dynamic Programming vs Divide-and-Conquer
published: true
description: Or Divide-and-Conquer on Steroids
tags: JavaScript, algorithms, webdev, computerscience
cover_image: https://thepracticaldev.s3.amazonaws.com/i/8gvm3qp23zo4ksvd5ngi.png
---

<div class="postArticle-content js-postField js-notesSource js-trackedPost" data-post-id="2fea680becbe" data-source="post_page" data-collection-id="5b301f10ddcd" data-tracking-context="postPage" data-scroll="native"><section name="0e61" class="section section--body section--first section--last"><div class="section-divider"><hr class="section-divider"></div><div class="section-content"><div class="section-inner sectionLayout--insetColumn"><h1 name="0ebd" id="0ebd" class="graf graf--h3 graf--leading graf--title">Or Divide-and-Conquer on Steroids</h1></div><div class="section-inner sectionLayout--fullWidth"><figure name="f141" id="f141" class="graf graf--figure graf--layoutFillWidth graf-after--h4" data-scroll="native"><div class="aspectRatioPlaceholder is-locked"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 16.5%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded is-imageLoaded" data-image-id="1*aRgXjJ6gv8sR59cu3sM64A.png" data-width="1600" data-height="264" data-is-featured="true" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*aRgXjJ6gv8sR59cu3sM64A.png?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="11"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/2000/1*aRgXjJ6gv8sR59cu3sM64A.png" src="https://cdn-images-1.medium.com/max/2000/1*aRgXjJ6gv8sR59cu3sM64A.png"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/2000/1*aRgXjJ6gv8sR59cu3sM64A.png"></noscript></div></div></figure></div><div class="section-inner sectionLayout--insetColumn"><h4 name="313a" id="313a" class="graf graf--h4 graf-after--figure">TL;DR</h4><p name="22d3" id="22d3" class="graf graf--p graf-after--h4">In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples: <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search" data-href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search" class="markup--anchor markup--p-anchor" rel="noopener nofollow" target="_blank"><strong class="markup--strong markup--p-strong">binary search</strong></a> and <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance" data-href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank"><strong class="markup--strong markup--p-strong">minimum edit distance</strong></a> (Levenshtein distance).</p><h4 name="59a6" id="59a6" class="graf graf--h4 graf-after--p">The Problem</h4><p name="c002" id="c002" class="graf graf--p graf-after--h4">When I <a href="https://github.com/trekhleb/javascript-algorithms" data-href="https://github.com/trekhleb/javascript-algorithms" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank"><strong class="markup--strong markup--p-strong">started to learn algorithms</strong></a> it was hard for me to understand the main idea of dynamic programming (<strong class="markup--strong markup--p-strong">DP</strong>) and how it is different from divide-and-conquer (<strong class="markup--strong markup--p-strong">DC</strong>) approach. When it gets to comparing those two paradigms usually Fibonacci function comes to the rescue as great <a href="https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming" data-href="https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">example</a>. But when we’re trying to solve the <strong class="markup--strong markup--p-strong">same</strong> problem using both DP and DC approaches to explain each of them, it feels for me like we may <strong class="markup--strong markup--p-strong">lose valuable detail</strong> that might help to catch the difference faster. And these detail tells us that each technique serves best for <strong class="markup--strong markup--p-strong">different</strong> types of problems.</p><p name="e627" id="e627" class="graf graf--p graf-after--p">I’m still in the process of understanding DP and DC difference and I can’t say that I’ve fully grasped the concepts so far. But I hope this article will shed some extra light and help you to do another step of learning such valuable algorithm paradigms as dynamic programming and divide-and-conquer.</p><h4 name="7912" id="7912" class="graf graf--h4 graf-after--p">Dynamic Programming and Divide-and-Conquer Similarities</h4><p name="9e7b" id="9e7b" class="graf graf--p graf-after--h4">As I see it for now I can say that <strong class="markup--strong markup--p-strong">dynamic programming is an extension of divide and conquer paradigm</strong>.</p><p name="0fb5" id="0fb5" class="graf graf--p graf-after--p">I would <strong class="markup--strong markup--p-strong">not</strong> treat them as something completely different. Because <strong class="markup--strong markup--p-strong">they</strong> <strong class="markup--strong markup--p-strong">both work by recursively breaking down a problem into two or more sub-problems</strong> of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.</p><p name="e1db" id="e1db" class="graf graf--p graf-after--p">So why do we still have different paradigm names then and why I called dynamic programming an extension. It is because dynamic programming approach may be applied to the problem <strong class="markup--strong markup--p-strong">only if the problem has certain</strong> <strong class="markup--strong markup--p-strong">restrictions or prerequisites</strong>. And after that dynamic programming <strong class="markup--strong markup--p-strong">extends</strong> divide and conquer approach with <strong class="markup--strong markup--p-strong">memoization</strong> or <strong class="markup--strong markup--p-strong">tabulation</strong> technique.</p><p name="af59" id="af59" class="graf graf--p graf-after--p">Let’s go step by step…</p><h4 name="95e2" id="95e2" class="graf graf--h4 graf-after--p">Dynamic Programming Prerequisites/Restrictions</h4><p name="8f45" id="8f45" class="graf graf--p graf-after--h4">As we’ve just discovered there are two key attributes that divide and conquer problem must have in order for dynamic programming to be applicable:</p><ol class="postList"><li name="d419" id="d419" class="graf graf--li graf-after--p"><a href="https://en.wikipedia.org/wiki/Optimal_substructure" data-href="https://en.wikipedia.org/wiki/Optimal_substructure" class="markup--anchor markup--li-anchor" rel="nofollow noopener" target="_blank">Optimal substructure</a>&#8202;—&#8202;optimal solution can be constructed from optimal solutions of its subproblems</li><li name="c852" id="c852" class="graf graf--li graf-after--li"><a href="https://en.wikipedia.org/wiki/Overlapping_subproblems" data-href="https://en.wikipedia.org/wiki/Overlapping_subproblems" class="markup--anchor markup--li-anchor" rel="nofollow noopener" target="_blank">Overlapping sub-problems</a>&#8202;—&#8202;problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems</li></ol><p name="c60e" id="c60e" class="graf graf--p graf-after--li">Once these two conditions are met we can say that this divide and conquer problem may be solved using dynamic programming approach.</p><h4 name="4b02" id="4b02" class="graf graf--h4 graf-after--p"><strong class="markup--strong markup--h4-strong">Dynamic Programming Extension for Divide and&nbsp;Conquer</strong></h4><p name="ac08" id="ac08" class="graf graf--p graf-after--h4">Dynamic programming approach extends divide and conquer approach with two techniques (<strong class="markup--strong markup--p-strong">memoization</strong> and <strong class="markup--strong markup--p-strong">tabulation</strong>) that both have a purpose of storing and re-using sub-problems solutions that may drastically improve performance. For example naive recursive implementation of Fibonacci function has time complexity of <code class="markup--code markup--p-code">O(2^n)</code> where DP solution doing the same with only <code class="markup--code markup--p-code">O(n)</code> time.</p><p name="4b0c" id="4b0c" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Memoization (top-down cache filling) </strong>refers to the technique of caching and reusing previously computed results. The memoized <code class="markup--code markup--p-code">fib</code> function would thus look like this:</p><pre name="296c" id="296c" class="graf graf--pre graf-after--p"><code class="markup--code markup--pre-code">memFib(n) {<br>    if (mem[n] is undefined)<br>        if (n &lt; 2) result = n<br>        else result = memFib(n-2) + memFib(n-1)<br>        mem[n] = result<br>    return mem[n]<br>}</code></pre><p name="f578" id="f578" class="graf graf--p graf-after--pre"><strong class="markup--strong markup--p-strong">Tabulation (bottom-up cache filling) </strong>is similar but focuses on filling the entries of the cache. Computing the values in the cache is easiest done iteratively. The tabulation version of <code class="markup--code markup--p-code">fib</code> would look like this:</p><pre name="f1f1" id="f1f1" class="graf graf--pre graf-after--p"><code class="markup--code markup--pre-code">tabFib(n) {<br>    mem[0] = 0<br>    mem[1] = 1<br>    for i = 2...n<br>        mem[i] = mem[i-2] + mem[i-1]<br>    return mem[n]<br>}</code></pre><p name="8de5" id="8de5" class="graf graf--p graf-after--pre">You may read more about memoization and tabulation comparison <a href="https://programming.guide/dynamic-programming-vs-memoization-vs-tabulation.html" data-href="https://programming.guide/dynamic-programming-vs-memoization-vs-tabulation.html" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">here</a>.</p><p name="f0e8" id="f0e8" class="graf graf--p graf-after--p">The main idea you should grasp here is that because our divide and conquer problem has overlapping sub-problems the caching of sub-problem solutions becomes possible and thus memoization/tabulation step up onto the scene.</p><h4 name="d057" id="d057" class="graf graf--h4 graf-after--p">So What the Difference Between DP and DC After&nbsp;All</h4><p name="bb91" id="bb91" class="graf graf--p graf-after--h4">Since we’re now familiar with DP prerequisites and its methodologies we’re ready to put all that was mentioned above into one picture.</p></div><div class="section-inner sectionLayout--outsetColumn"><figure name="683f" id="683f" class="graf graf--figure graf--layoutOutsetCenter graf-after--p" data-scroll="native"><div class="aspectRatioPlaceholder is-locked" style="max-width: 1000px; max-height: 561px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 56.10000000000001%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*BwuDAdImyK_nZpb-H8h3SA.jpeg" data-width="1407" data-height="790" data-action="zoom" data-action-value="1*BwuDAdImyK_nZpb-H8h3SA.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*BwuDAdImyK_nZpb-H8h3SA.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="41"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/2000/1*BwuDAdImyK_nZpb-H8h3SA.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/2000/1*BwuDAdImyK_nZpb-H8h3SA.jpeg"></noscript></div></div><figcaption class="imageCaption">Dynamic programming and divide and conquer paradigms dependency</figcaption></figure></div><div class="section-inner sectionLayout--insetColumn"><p name="c20e" id="c20e" class="graf graf--p graf-after--figure">Let’s go and try to solve some problems using DP and DC approaches to make this illustration more clear.</p><h4 name="6cdd" id="6cdd" class="graf graf--h4 graf-after--p">Divide and Conquer Example: Binary&nbsp;Search</h4><p name="3756" id="3756" class="graf graf--p graf-after--h4"><a href="https://en.wikipedia.org/wiki/Binary_search_algorithm" data-href="https://en.wikipedia.org/wiki/Binary_search_algorithm" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">Binary search</a> algorithm, also known as half-interval search, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.</p><p name="0ff0" id="0ff0" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Example</strong></p><p name="2ac1" id="2ac1" class="graf graf--p graf-after--p">Here is a visualization of the binary search algorithm where <code class="markup--code markup--p-code">4</code> is the target value.</p><figure name="8cf0" id="8cf0" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 436px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 62.3%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*YX5dC6S94p0_obaXxkOz9Q.jpeg" data-width="1104" data-height="688" data-action="zoom" data-action-value="1*YX5dC6S94p0_obaXxkOz9Q.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*YX5dC6S94p0_obaXxkOz9Q.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="46"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*YX5dC6S94p0_obaXxkOz9Q.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*YX5dC6S94p0_obaXxkOz9Q.jpeg"></noscript></div></div><figcaption class="imageCaption">Binary search algorithm logic</figcaption></figure><p name="a8cf" id="a8cf" class="graf graf--p graf-after--figure">Let’s draw the same logic but in form of decision tree.</p><figure name="8473" id="8473" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 542px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 77.5%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*NmOhla4b399yxLsYR-rk0g.jpeg" data-width="830" data-height="643" data-action="zoom" data-action-value="1*NmOhla4b399yxLsYR-rk0g.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*NmOhla4b399yxLsYR-rk0g.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="57"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*NmOhla4b399yxLsYR-rk0g.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*NmOhla4b399yxLsYR-rk0g.jpeg"></noscript></div></div><figcaption class="imageCaption">Binary search algorithm decision&nbsp;tree</figcaption></figure><p name="d17f" id="d17f" class="graf graf--p graf-after--figure">You may clearly see here a divide and conquer principle of solving the problem. We’re iteratively breaking the original array into sub-arrays and trying to find required element in there.</p><p name="6c75" id="6c75" class="graf graf--p graf-after--p">Can we apply dynamic programming to it? <strong class="markup--strong markup--p-strong">No.</strong> It is because <strong class="markup--strong markup--p-strong">there are no overlapping sub-problems</strong>. Every time we split the array into completely independent parts. And according to divide and conquer prerequisites/restrictions the sub-problems <strong class="markup--strong markup--p-strong">must be</strong> overlapped somehow.</p><p name="9269" id="9269" class="graf graf--p graf-after--p">Normally every time you draw a decision tree and it is actually a <strong class="markup--strong markup--p-strong">tree</strong> (and <strong class="markup--strong markup--p-strong">not</strong> a decision <strong class="markup--strong markup--p-strong">graph</strong>) it would mean that you don’t have overlapping sub-problems and this is not dynamic programming problem.</p><p name="f55c" id="f55c" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">The Code</strong></p><p name="6c7a" id="6c7a" class="graf graf--p graf-after--p"><a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search" data-href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">Here</a> you may find complete source code of binary search function with test cases and explanations.</p><pre name="537a" id="537a" class="graf graf--pre graf-after--p">function binarySearch(sortedArray, seekElement) {<br>  let startIndex = 0;<br>  let endIndex = sortedArray.length - 1;</pre><pre name="5f7c" id="5f7c" class="graf graf--pre graf-after--pre">  while (startIndex &lt;= endIndex) {<br>    const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2);</pre><pre name="e6fc" id="e6fc" class="graf graf--pre graf-after--pre">    // If we've found the element just return its position.<br>    if (sortedArray[middleIndex] === seekElement)) {<br>      return middleIndex;<br>    }</pre><pre name="f375" id="f375" class="graf graf--pre graf-after--pre">    // Decide which half to choose: left or right one.<br>    if (sortedArray[middleIndex] &lt; seekElement)) {<br>      // Go to the right half of the array.<br>      startIndex = middleIndex + 1;<br>    } else {<br>      // Go to the left half of the array.<br>      endIndex = middleIndex - 1;<br>    }<br>  }</pre><pre name="343e" id="343e" class="graf graf--pre graf-after--pre">  return -1;<br>}</pre><h4 name="46b7" id="46b7" class="graf graf--h4 graf-after--pre">Dynamic Programming Example: Minimum Edit&nbsp;Distance</h4><p name="af46" id="af46" class="graf graf--p graf-after--h4">Normally when it comes to dynamic programming examples the <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci" data-href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">Fibonacci</a> number algorithm is being taken by default. But let’s take a little bit more complex algorithm to have some kind of variety that should help us to grasp the concept.</p><p name="3def" id="3def" class="graf graf--p graf-after--p"><a href="https://en.wikipedia.org/wiki/Levenshtein_distance" data-href="https://en.wikipedia.org/wiki/Levenshtein_distance" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">Minimum Edit Distance</a> (or Levenshtein Distance) is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (<em class="markup--em markup--p-em">insertions, deletions or substitutions</em>) required to change one word into the other.</p><p name="4ff9" id="4ff9" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Example</strong></p><p name="5f20" id="5f20" class="graf graf--p graf-after--p">For<strong class="markup--strong markup--p-strong"> </strong>example, the Levenshtein distance between “kitten” and “sitting” is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:</p><ol class="postList"><li name="e2ec" id="e2ec" class="graf graf--li graf-after--p"><strong class="markup--strong markup--li-strong">k</strong>itten → <strong class="markup--strong markup--li-strong">s</strong>itten (substitution of “s” for “k”)</li><li name="c416" id="c416" class="graf graf--li graf-after--li">sitt<strong class="markup--strong markup--li-strong">e</strong>n → sitt<strong class="markup--strong markup--li-strong">i</strong>n (substitution of “i” for “e”)</li><li name="daff" id="daff" class="graf graf--li graf-after--li">sittin → sittin<strong class="markup--strong markup--li-strong">g</strong> (insertion of “g” at the end).</li></ol><p name="1825" id="1825" class="graf graf--p graf-after--li"><strong class="markup--strong markup--p-strong">Applications</strong></p><p name="5c71" id="5c71" class="graf graf--p graf-after--p">This has a wide range of applications, for instance, spell checkers, correction systems for optical character recognition, fuzzy string searching, and software to assist natural language translation based on translation memory.</p><p name="deb2" id="deb2" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Mathematical Definition</strong></p><p name="009c" id="009c" class="graf graf--p graf-after--p">Mathematically, the Levenshtein distance between two strings <code class="markup--code markup--p-code">a</code>, <code class="markup--code markup--p-code">b</code> (of length <code class="markup--code markup--p-code">|a|</code> and <code class="markup--code markup--p-code">|b|</code> respectively) is given by function <code class="markup--code markup--p-code">lev(|a|, |b|)</code> where</p><figure name="0ca3" id="0ca3" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 130px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 18.6%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*njxdMX6ChqZIAnaqd6NZlQ.png" data-width="1096" data-height="204" data-action="zoom" data-action-value="1*njxdMX6ChqZIAnaqd6NZlQ.png" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*njxdMX6ChqZIAnaqd6NZlQ.png?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="13"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*njxdMX6ChqZIAnaqd6NZlQ.png"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*njxdMX6ChqZIAnaqd6NZlQ.png"></noscript></div></div></figure><p name="5ba5" id="5ba5" class="graf graf--p graf-after--figure">Note that the first element in the minimum corresponds to <strong class="markup--strong markup--p-strong">deletion</strong> (from <code class="markup--code markup--p-code">a</code> to <code class="markup--code markup--p-code">b</code>), the second to <strong class="markup--strong markup--p-strong">insertion</strong> and the third to <strong class="markup--strong markup--p-strong">match</strong> <strong class="markup--strong markup--p-strong">or mismatch</strong>, depending on whether the respective symbols are the same.</p><p name="dc7b" id="dc7b" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Explanation</strong></p><p name="6fb5" id="6fb5" class="graf graf--p graf-after--p">Ok, let’s try to figure out what that formula is talking about. Let’s take a simple example of finding minimum edit distance between strings <strong class="markup--strong markup--p-strong">ME</strong> and <strong class="markup--strong markup--p-strong">MY</strong>. Intuitively you already know that minimum edit distance here is <strong class="markup--strong markup--p-strong">1</strong> operation and this operation is “<em class="markup--em markup--p-em">replace </em><strong class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">E</em></strong><em class="markup--em markup--p-em"> with </em><strong class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">Y</em></strong>”. But let’s try to formalize it in a form of the algorithm in order to be able to do more complex examples like transforming <strong class="markup--strong markup--p-strong">Saturday</strong> into <strong class="markup--strong markup--p-strong">Sunday</strong>.</p><p name="2d55" id="2d55" class="graf graf--p graf-after--p">To apply the formula to <em class="markup--em markup--p-em">M</em><strong class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">E</em></strong><em class="markup--em markup--p-em">→M</em><strong class="markup--strong markup--p-strong"><em class="markup--em markup--p-em">Y</em></strong> transformation we need to know minimum edit distances of <em class="markup--em markup--p-em">ME→M</em>, <em class="markup--em markup--p-em">M→MY</em> and <em class="markup--em markup--p-em">M→M </em>transformations in prior. Then we will need to pick the minimum one and add +1 operation to transform last letters <em class="markup--em markup--p-em">E→Y</em>.</p><p name="396a" id="396a" class="graf graf--p graf-after--p">So we can already see here a recursive nature of the solution: minimum edit distance of <em class="markup--em markup--p-em">ME→MY</em> transformation is being calculated based on three previously possible transformations. Thus we may say that this is <strong class="markup--strong markup--p-strong">divide and conquer algorithm</strong>.</p><p name="cf63" id="cf63" class="graf graf--p graf-after--p">To explain this further let’s draw the following matrix.</p><figure name="8e31" id="8e31" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 355px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 50.7%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*2d46ug_PL5LfeqztckoYGw.jpeg" data-width="1371" data-height="695" data-action="zoom" data-action-value="1*2d46ug_PL5LfeqztckoYGw.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*2d46ug_PL5LfeqztckoYGw.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="37"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*2d46ug_PL5LfeqztckoYGw.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*2d46ug_PL5LfeqztckoYGw.jpeg"></noscript></div></div><figcaption class="imageCaption">Simple example of finding minimum edit distance between ME and MY&nbsp;strings</figcaption></figure><p name="daa1" id="daa1" class="graf graf--p graf-after--figure"><strong class="markup--strong markup--p-strong">Cell (0,1)</strong> contains red number 1. It means that we need 1 operation to transform <strong class="markup--strong markup--p-strong">M</strong> to <strong class="markup--strong markup--p-strong">empty string</strong>: delete <strong class="markup--strong markup--p-strong">M</strong>. This is why this number is red.</p><p name="9bfd" id="9bfd" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Cell (0,2)</strong> contains red number 2. It means that we need 2 operations to transform <strong class="markup--strong markup--p-strong">ME</strong> to <strong class="markup--strong markup--p-strong">empty string</strong>: delete <strong class="markup--strong markup--p-strong">E</strong>, delete <strong class="markup--strong markup--p-strong">M</strong>.</p><p name="3c17" id="3c17" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Cell (1,0)</strong> contains green number 1. It means that we need 1 operation to transform empty string to <strong class="markup--strong markup--p-strong">M</strong>: insert <strong class="markup--strong markup--p-strong">M</strong>. This is why this number is green.</p><p name="bf0b" id="bf0b" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Cell (2,0)</strong> contains green number 2. It means that we need 2 operations to transform empty string to <strong class="markup--strong markup--p-strong">MY</strong>: insert <strong class="markup--strong markup--p-strong">Y</strong>, insert <strong class="markup--strong markup--p-strong">M</strong>.</p><p name="5b84" id="5b84" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Cell (1,1) </strong>contains number 0. It means that it costs nothing to transform <strong class="markup--strong markup--p-strong">M</strong> to <strong class="markup--strong markup--p-strong">M</strong>.</p><p name="a115" id="a115" class="graf graf--p graf-after--p"><strong class="markup--strong markup--p-strong">Cell (1,2)</strong> contains red number 1. It means that we need 1 operation to transform <strong class="markup--strong markup--p-strong">ME</strong> to <strong class="markup--strong markup--p-strong">M</strong>: delete <strong class="markup--strong markup--p-strong">E</strong>.</p><p name="5b45" id="5b45" class="graf graf--p graf-after--p">And so on…</p><p name="f747" id="f747" class="graf graf--p graf-after--p">This looks easy for such small matrix as ours (it is only 3x3). But how we could calculate all those numbers for bigger matrices (let’s say 9x7 one, for Saturday<em class="markup--em markup--p-em">→</em>Sunday transformation)?</p><p name="178d" id="178d" class="graf graf--p graf-after--p">The good news is that according to the formula you only need three adjacent cells <code class="markup--code markup--p-code">(i-1,j)</code>, <code class="markup--code markup--p-code">(i-1,j-1)</code>, and <code class="markup--code markup--p-code">(i,j-1)</code> to calculate the number for current cell <code class="markup--code markup--p-code">(i,j)</code>&nbsp;. All we need to do is to find the minimum of those three cells and then add +1 in case if we have different letters in <code class="markup--code markup--p-code">i</code>-s row and <code class="markup--code markup--p-code">j</code>-s column</p><p name="f354" id="f354" class="graf graf--p graf-after--p">So once again you may clearly see the recursive nature of the problem.</p><figure name="ed6e" id="ed6e" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 276px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 39.5%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*JdHQ5TeKiDlE-iKK1s_2vw.jpeg" data-width="1166" data-height="460" data-action="zoom" data-action-value="1*JdHQ5TeKiDlE-iKK1s_2vw.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*JdHQ5TeKiDlE-iKK1s_2vw.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="28"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*JdHQ5TeKiDlE-iKK1s_2vw.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*JdHQ5TeKiDlE-iKK1s_2vw.jpeg"></noscript></div></div><figcaption class="imageCaption">Recursive nature of minimum edit distance&nbsp;problem</figcaption></figure><p name="f7d1" id="f7d1" class="graf graf--p graf-after--figure">Ok we’ve just found out that we’re dealing with divide and conquer problem here. But can we apply dynamic programming approach to it? Does this problem satisfies our <strong class="markup--strong markup--p-strong">overlapping sub-problems</strong> and <strong class="markup--strong markup--p-strong">optimal substructure</strong> restrictions? <strong class="markup--strong markup--p-strong">Yes</strong>. Let’s see it from decision graph.</p><figure name="f1ab" id="f1ab" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 316px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 45.1%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*SGwYUpXH9H1xUeTvJk0e7Q.jpeg" data-width="1521" data-height="686" data-action="zoom" data-action-value="1*SGwYUpXH9H1xUeTvJk0e7Q.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*SGwYUpXH9H1xUeTvJk0e7Q.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="33"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*SGwYUpXH9H1xUeTvJk0e7Q.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*SGwYUpXH9H1xUeTvJk0e7Q.jpeg"></noscript></div></div><figcaption class="imageCaption">Decision graph for minimum edit distance with overlapping sub-problems</figcaption></figure><p name="5ce1" id="5ce1" class="graf graf--p graf-after--figure">First of all this is <strong class="markup--strong markup--p-strong">not</strong> a decision <strong class="markup--strong markup--p-strong">tree</strong>. It is a decision <strong class="markup--strong markup--p-strong">graph</strong>. You may see a number of <strong class="markup--strong markup--p-strong">overlapping subproblems</strong> on the picture that are marked with red. Also there is no way to reduce the number of operations and make it less then a minimum of those three adjacent cells from the formula.</p><p name="49dd" id="49dd" class="graf graf--p graf-after--p">Also you may notice that each cell number in the matrix is being calculated based on previous ones. Thus the <strong class="markup--strong markup--p-strong">tabulation</strong> technique (filling the cache in bottom-up direction) is being applied here. You’ll see it in code example below.</p><p name="f96f" id="f96f" class="graf graf--p graf-after--p">Applying this principles further we may solve more complicated cases like with Saturday<em class="markup--em markup--p-em">→</em>Sunday transformation.</p><figure name="bbb7" id="bbb7" class="graf graf--figure graf-after--p"><div class="aspectRatioPlaceholder is-locked" style="max-width: 700px; max-height: 456px;"><div class="aspectRatioPlaceholder-fill" style="padding-bottom: 65.2%;"></div><div class="progressiveMedia js-progressiveMedia graf-image is-canvasLoaded" data-image-id="1*fPEHiImYLKxSTUhrGbYq3g.jpeg" data-width="1158" data-height="755" data-action="zoom" data-action-value="1*fPEHiImYLKxSTUhrGbYq3g.jpeg" data-scroll="native"><img src="https://cdn-images-1.medium.com/freeze/max/60/1*fPEHiImYLKxSTUhrGbYq3g.jpeg?q=20" crossorigin="anonymous" class="progressiveMedia-thumbnail js-progressiveMedia-thumbnail"><canvas class="progressiveMedia-canvas js-progressiveMedia-canvas" width="75" height="48"></canvas><img class="progressiveMedia-image js-progressiveMedia-image" data-src="https://cdn-images-1.medium.com/max/1600/1*fPEHiImYLKxSTUhrGbYq3g.jpeg"><noscript class="js-progressiveMedia-inner"><img class="progressiveMedia-noscript js-progressiveMedia-inner" src="https://cdn-images-1.medium.com/max/1600/1*fPEHiImYLKxSTUhrGbYq3g.jpeg"></noscript></div></div><figcaption class="imageCaption">Minimum edit distance to convert Saturday to&nbsp;Sunday</figcaption></figure><p name="af4d" id="af4d" class="graf graf--p graf-after--figure"><strong class="markup--strong markup--p-strong">The Code</strong></p><p name="0c94" id="0c94" class="graf graf--p graf-after--p"><a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance" data-href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">Here</a> you may find complete source code of minimum edit distance function with test cases and explanations.</p><pre name="e275" id="e275" class="graf graf--pre graf-after--p">function levenshteinDistance(a, b) {<br>  const distanceMatrix = Array(b.length + 1)<br>    .fill(null)<br>    .map(<br>      () =&gt; Array(a.length + 1).fill(null)<br>    );</pre><pre name="5e6b" id="5e6b" class="graf graf--pre graf-after--pre">  for (let i = 0; i &lt;= a.length; i += 1) {<br>    distanceMatrix[0][i] = i;<br>  }</pre><pre name="facf" id="facf" class="graf graf--pre graf-after--pre">  for (let j = 0; j &lt;= b.length; j += 1) {<br>    distanceMatrix[j][0] = j;<br>  }</pre><pre name="8785" id="8785" class="graf graf--pre graf-after--pre">  for (let j = 1; j &lt;= b.length; j += 1) {<br>    for (let i = 1; i &lt;= a.length; i += 1) {<br>      const indicator = a[i - 1] === b[j - 1] ? 0 : 1;<br>      <br>      distanceMatrix[j][i] = Math.min(<br>        distanceMatrix[j][i - 1] + 1, // deletion<br>        distanceMatrix[j - 1][i] + 1, // insertion<br>        distanceMatrix[j - 1][i - 1] + indicator, // substitution<br>      );<br>    }<br>  }</pre><pre name="0337" id="0337" class="graf graf--pre graf-after--pre">  return distanceMatrix[b.length][a.length];<br>}</pre><h4 name="589a" id="589a" class="graf graf--h4 graf-after--pre">Conclusion</h4><p name="9fd4" id="9fd4" class="graf graf--p graf-after--h4">In this article we have compared two algorithmic approaches such as dynamic programming and divide-and-conquer. We’ve found out that dynamic programing is based on divide and conquer principle and may be applied only if the problem has overlapping sub-problems and optimal substructure (like in Levenshtein distance case). Dynamic programming then is using memoization or tabulation technique to store solutions of overlapping sub-problems for later usage.</p><p name="7cd0" id="7cd0" class="graf graf--p graf-after--p">I hope this article hasn’t brought you more confusion but rather shed some light on these two important algorithmic concepts!&nbsp;:)</p><p name="5b52" id="5b52" class="graf graf--p graf-after--p">You may find more examples of divide and conquer and dynamic programming problems with explanations, comments and test cases in <a href="https://github.com/trekhleb/javascript-algorithms" data-href="https://github.com/trekhleb/javascript-algorithms" class="markup--anchor markup--p-anchor" rel="nofollow noopener" target="_blank">JavaScript Algorithms and Data Structures</a> repository.</p><p name="0dc0" id="0dc0" class="graf graf--p graf-after--p graf--trailing">Happy coding!</p></div></div></section></div>