-
-
Notifications
You must be signed in to change notification settings - Fork 21
/
index.html
97 lines (91 loc) · 92.7 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
<!DOCTYPE html><html><head><meta charSet="utf-8"/><meta http-equiv="x-ua-compatible" content="ie=edge"/><meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"/><style data-href="/styles.f4dbc894744c3c869f21.css" id="gatsby-global-css">@import url(https://fonts.googleapis.com/css2?family=Roboto:ital,wght@0,100;0,300;0,400;0,500;0,700;0,900;1,100;1,300;1,400;1,500;1,700;1,900&display=swap);.post--2021--binary-floating-point--bit-button:hover{box-shadow:0 0 5px 1px rgba(0,0,0,.2);transition:box-shadow .2s ease-in-out}input:checked~.toggle__dot{transform:translateX(100%)}input:checked~.toggle__line{background-color:#48bb78}.post--2021--water-line--gyro-cube .gyro-cube-container{height:400px;display:flex;justify-content:center;align-items:center;perspective:800px;perspective-origin:50%}.post--2021--water-line--gyro-cube .gyro-cube{position:relative;width:200px;height:200px;transform-style:preserve-3d}.post--2021--water-line--gyro-cube .gyro-cube-side{position:absolute;width:100%;height:100%;opacity:.8;border:2px solid #fff;display:flex;justify-content:center;align-items:center;color:#fff;font-weight:700;font-size:100px}.post--2021--water-line--gyro-cube .gyro-cube-front{background-color:#d50000;transform:translateZ(100px)}.post--2021--water-line--gyro-cube .gyro-cube-back{background-color:#a0f;transform:translateZ(-100px)}.post--2021--water-line--gyro-cube .gyro-cube-left{background-color:#304ffe;transform:translateX(100px) rotateY(90deg)}.post--2021--water-line--gyro-cube .gyro-cube-right{background-color:#0091ea;transform:translateX(-100px) rotateY(90deg)}.post--2021--water-line--gyro-cube .gyro-cube-top{background-color:#00bfa5;transform:translateY(-100px) rotateX(90deg)}.post--2021--water-line--gyro-cube .gyro-cube-bottom{background-color:#64dd17;transform:translateY(100px) rotateX(90deg)}.custom-fade-in-opacity{opacity:1;-webkit-animation-name:customFadeInOpacity;animation-name:customFadeInOpacity;-webkit-animation-iteration-count:1;animation-iteration-count:1;-webkit-animation-timing-function:ease-out;animation-timing-function:ease-out;-webkit-animation-duration:.8s;animation-duration:.8s}@-webkit-keyframes customFadeInOpacity{0%{opacity:0}to{opacity:1}}@keyframes customFadeInOpacity{0%{opacity:0}to{opacity:1}}.prose blockquote p:first-of-type:before,.prose blockquote p:last-of-type:after,.prose code:after,.prose code:before{content:""!important}.prose blockquote{font-weight:400!important}.prose li code.language-text,.prose p code.language-text,.prose td code.language-text,.prose th code.language-text,.prose tr code.language-text{padding:2px 5px 1px;font-weight:400}.prose p>img{margin:auto}.prose h1>a.gatsby-remark-autolink-header-anchor,.prose h2>a.gatsby-remark-autolink-header-anchor,.prose h3>a.gatsby-remark-autolink-header-anchor,.prose h4>a.gatsby-remark-autolink-header-anchor,.prose h5>a.gatsby-remark-autolink-header-anchor{visibility:hidden;display:inline-block;margin-left:10px}.prose h1:hover>a.gatsby-remark-autolink-header-anchor,.prose h2:hover>a.gatsby-remark-autolink-header-anchor,.prose h3:hover>a.gatsby-remark-autolink-header-anchor,.prose h4:hover>a.gatsby-remark-autolink-header-anchor,.prose h5:hover>a.gatsby-remark-autolink-header-anchor{visibility:visible}
/* ! tailwindcss v2.1.2 | MIT License | https://tailwindcss.com */
/*! modern-normalize v1.0.0 | MIT License | https://github.com/sindresorhus/modern-normalize */:root{-moz-tab-size:4;-o-tab-size:4;tab-size:4}html{line-height:1.15;-webkit-text-size-adjust:100%}body{margin:0;font-family:system-ui,-apple-system,Segoe UI,Roboto,Helvetica,Arial,sans-serif,Apple Color Emoji,Segoe UI Emoji}hr{height:0;color:inherit}abbr[title]{-webkit-text-decoration:underline dotted;text-decoration:underline dotted}b,strong{font-weight:bolder}code,kbd,pre,samp{font-family:ui-monospace,SFMono-Regular,Consolas,Liberation Mono,Menlo,monospace;font-size:1em}small{font-size:80%}sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline}sub{bottom:-.25em}sup{top:-.5em}table{text-indent:0;border-color:inherit}button,input,optgroup,select,textarea{font-family:inherit;font-size:100%;line-height:1.15;margin:0}button,select{text-transform:none}[type=button],[type=reset],[type=submit],button{-webkit-appearance:button}legend{padding:0}progress{vertical-align:baseline}[type=search]{-webkit-appearance:textfield;outline-offset:-2px}summary{display:list-item}blockquote,dd,dl,figure,h1,h2,h3,h4,h5,h6,hr,p,pre{margin:0}button{background-color:transparent;background-image:none}button:focus{outline:1px dotted;outline:5px auto -webkit-focus-ring-color}fieldset,ol,ul{margin:0;padding:0}ol,ul{list-style:none}html{font-family:Roboto,ui-sans-serif,system-ui,-apple-system,BlinkMacSystemFont,Segoe UI,Helvetica Neue,Arial,Noto Sans,sans-serif,Apple Color Emoji,Segoe UI Emoji,Segoe UI Symbol,Noto Color Emoji;line-height:1.5}body{font-family:inherit;line-height:inherit}*,:after,:before{box-sizing:border-box;border:0 solid #e5e7eb}hr{border-top-width:1px}img{border-style:solid}textarea{resize:vertical}input::-moz-placeholder,textarea::-moz-placeholder{opacity:1;color:#9ca3af}input:-ms-input-placeholder,textarea:-ms-input-placeholder{opacity:1;color:#9ca3af}input::placeholder,textarea::placeholder{opacity:1;color:#9ca3af}button{cursor:pointer}table{border-collapse:collapse}h1,h2,h3,h4,h5,h6{font-size:inherit;font-weight:inherit}a{color:inherit;text-decoration:inherit}button,input,optgroup,select,textarea{padding:0;line-height:inherit;color:inherit}code,kbd,pre,samp{font-family:ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,Liberation Mono,Courier New,monospace}audio,canvas,embed,iframe,img,object,svg,video{display:block;vertical-align:middle}img,video{max-width:100%;height:auto}.container{width:100%}@media (min-width:640px){.container{max-width:640px}}@media (min-width:768px){.container{max-width:768px}}@media (min-width:1024px){.container{max-width:1024px}}@media (min-width:1280px){.container{max-width:1280px}}@media (min-width:1536px){.container{max-width:1536px}}.prose{color:#374151;max-width:65ch}.prose [class~=lead]{color:#4b5563;font-size:1.25em;line-height:1.6;margin-top:1.2em;margin-bottom:1.2em}.prose a{color:#dc2626;text-decoration:underline;font-weight:500}.prose a:hover{color:#ef4444}.prose strong{color:#111827;font-weight:600}.prose ol[type=A]{--list-counter-style:upper-alpha}.prose ol[type=a]{--list-counter-style:lower-alpha}.prose ol[type=I]{--list-counter-style:upper-roman}.prose ol[type=i]{--list-counter-style:lower-roman}.prose ol[type="1"]{--list-counter-style:decimal}.prose ol>li{position:relative;padding-left:1.75em}.prose ol>li:before{content:counter(list-item,var(--list-counter-style,decimal)) ".";position:absolute;font-weight:400;color:#6b7280;left:0}.prose ul>li{position:relative;padding-left:1.75em}.prose ul>li:before{content:"";position:absolute;background-color:#d1d5db;border-radius:50%;width:.375em;height:.375em;top:.6875em;left:.25em}.prose hr{border-color:#e5e7eb;border-top-width:1px;margin-top:3em;margin-bottom:3em}.prose blockquote{font-weight:500;font-style:italic;color:#111827;border-left-width:.25rem;border-left-color:#e5e7eb;quotes:"\201C""\201D""\2018""\2019";margin-top:1.6em;margin-bottom:1.6em;padding-left:1em}.prose blockquote p:first-of-type:before{content:open-quote}.prose blockquote p:last-of-type:after{content:close-quote}.prose h1{color:#111827;font-weight:800;font-size:2.25em;margin-top:0;margin-bottom:.8888889em;line-height:1.1111111}.prose h2{color:#111827;font-weight:700;font-size:1.5em;margin-top:2em;margin-bottom:1em;line-height:1.3333333}.prose h3{font-size:1.25em;margin-top:1.6em;margin-bottom:.6em;line-height:1.6}.prose h3,.prose h4{color:#111827;font-weight:600}.prose h4{margin-top:1.5em;margin-bottom:.5em;line-height:1.5}.prose figure figcaption{color:#6b7280;font-size:.875em;line-height:1.4285714;margin-top:.8571429em}.prose code{color:#111827;font-weight:600;font-size:.875em}.prose code:after,.prose code:before{content:"`"}.prose a code{color:#111827}.prose pre{color:#e5e7eb;background-color:#1f2937;overflow-x:auto;font-size:.875em;line-height:1.7142857;margin-top:1.7142857em;margin-bottom:1.7142857em;border-radius:.375rem;padding:.8571429em 1.1428571em}.prose pre code{background-color:transparent;border-width:0;border-radius:0;padding:0;font-weight:400;color:inherit;font-size:inherit;font-family:inherit;line-height:inherit}.prose pre code:after,.prose pre code:before{content:none}.prose table{width:100%;table-layout:auto;text-align:left;margin-top:2em;margin-bottom:2em;font-size:.875em;line-height:1.7142857}.prose thead{color:#111827;font-weight:600;border-bottom-width:1px;border-bottom-color:#d1d5db}.prose thead th{vertical-align:bottom;padding-right:.5714286em;padding-bottom:.5714286em;padding-left:.5714286em}.prose tbody tr{border-bottom-width:1px;border-bottom-color:#e5e7eb}.prose tbody tr:last-child{border-bottom-width:0}.prose tbody td{vertical-align:top;padding:.5714286em}.prose{font-size:1rem;line-height:1.75}.prose p{margin-top:1.25em;margin-bottom:1.25em}.prose figure,.prose img,.prose video{margin-top:2em;margin-bottom:2em}.prose figure>*{margin-top:0;margin-bottom:0}.prose h2 code{font-size:.875em}.prose h3 code{font-size:.9em}.prose ol,.prose ul{margin-top:1.25em;margin-bottom:1.25em}.prose li{margin-top:.5em;margin-bottom:.5em}.prose>ul>li p{margin-top:.75em;margin-bottom:.75em}.prose>ul>li>:first-child{margin-top:1.25em}.prose>ul>li>:last-child{margin-bottom:1.25em}.prose>ol>li>:first-child{margin-top:1.25em}.prose>ol>li>:last-child{margin-bottom:1.25em}.prose ol ol,.prose ol ul,.prose ul ol,.prose ul ul{margin-top:.75em;margin-bottom:.75em}.prose h2+*,.prose h3+*,.prose h4+*,.prose hr+*{margin-top:0}.prose thead th:first-child{padding-left:0}.prose thead th:last-child{padding-right:0}.prose tbody td:first-child{padding-left:0}.prose tbody td:last-child{padding-right:0}.prose>:first-child{margin-top:0}.prose>:last-child{margin-bottom:0}.prose-sm{font-size:.875rem;line-height:1.7142857}.prose-sm p{margin-top:1.1428571em;margin-bottom:1.1428571em}.prose-sm [class~=lead]{font-size:1.2857143em;line-height:1.5555556;margin-top:.8888889em;margin-bottom:.8888889em}.prose-sm blockquote{margin-top:1.3333333em;margin-bottom:1.3333333em;padding-left:1.1111111em}.prose-sm h1{font-size:2.1428571em;margin-top:0;margin-bottom:.8em;line-height:1.2}.prose-sm h2{font-size:1.4285714em;margin-top:1.6em;margin-bottom:.8em;line-height:1.4}.prose-sm h3{font-size:1.2857143em;margin-top:1.5555556em;margin-bottom:.4444444em;line-height:1.5555556}.prose-sm h4{margin-top:1.4285714em;margin-bottom:.5714286em;line-height:1.4285714}.prose-sm figure,.prose-sm img,.prose-sm video{margin-top:1.7142857em;margin-bottom:1.7142857em}.prose-sm figure>*{margin-top:0;margin-bottom:0}.prose-sm figure figcaption{font-size:.8571429em;line-height:1.3333333;margin-top:.6666667em}.prose-sm code{font-size:.8571429em}.prose-sm h2 code{font-size:.9em}.prose-sm h3 code{font-size:.8888889em}.prose-sm pre{font-size:.8571429em;line-height:1.6666667;margin-top:1.6666667em;margin-bottom:1.6666667em;border-radius:.25rem;padding:.6666667em 1em}.prose-sm ol,.prose-sm ul{margin-top:1.1428571em;margin-bottom:1.1428571em}.prose-sm li{margin-top:.2857143em;margin-bottom:.2857143em}.prose-sm ol>li{padding-left:1.5714286em}.prose-sm ol>li:before{left:0}.prose-sm ul>li{padding-left:1.5714286em}.prose-sm ul>li:before{height:.3571429em;width:.3571429em;top:.67857em;left:.2142857em}.prose-sm>ul>li p{margin-top:.5714286em;margin-bottom:.5714286em}.prose-sm>ul>li>:first-child{margin-top:1.1428571em}.prose-sm>ul>li>:last-child{margin-bottom:1.1428571em}.prose-sm>ol>li>:first-child{margin-top:1.1428571em}.prose-sm>ol>li>:last-child{margin-bottom:1.1428571em}.prose-sm ol ol,.prose-sm ol ul,.prose-sm ul ol,.prose-sm ul ul{margin-top:.5714286em;margin-bottom:.5714286em}.prose-sm hr{margin-top:2.8571429em;margin-bottom:2.8571429em}.prose-sm h2+*,.prose-sm h3+*,.prose-sm h4+*,.prose-sm hr+*{margin-top:0}.prose-sm table{font-size:.8571429em;line-height:1.5}.prose-sm thead th{padding-right:1em;padding-bottom:.6666667em;padding-left:1em}.prose-sm thead th:first-child{padding-left:0}.prose-sm thead th:last-child{padding-right:0}.prose-sm tbody td{padding:.6666667em 1em}.prose-sm tbody td:first-child{padding-left:0}.prose-sm tbody td:last-child{padding-right:0}.prose-sm>:first-child{margin-top:0}.prose-sm>:last-child{margin-bottom:0}.prose-red a,.prose-red a code{color:#dc2626}.appearance-none{-webkit-appearance:none;-moz-appearance:none;appearance:none}.bg-black{--tw-bg-opacity:1;background-color:rgba(0,0,0,var(--tw-bg-opacity))}.bg-white{--tw-bg-opacity:1;background-color:rgba(255,255,255,var(--tw-bg-opacity))}.bg-gray-100{--tw-bg-opacity:1;background-color:rgba(243,244,246,var(--tw-bg-opacity))}.bg-gray-200{--tw-bg-opacity:1;background-color:rgba(229,231,235,var(--tw-bg-opacity))}.bg-gray-400{--tw-bg-opacity:1;background-color:rgba(156,163,175,var(--tw-bg-opacity))}.bg-red-100{--tw-bg-opacity:1;background-color:rgba(254,226,226,var(--tw-bg-opacity))}.bg-blue-100{--tw-bg-opacity:1;background-color:rgba(219,234,254,var(--tw-bg-opacity))}.hover\:bg-black:hover{--tw-bg-opacity:1;background-color:rgba(0,0,0,var(--tw-bg-opacity))}.hover\:bg-white:hover{--tw-bg-opacity:1;background-color:rgba(255,255,255,var(--tw-bg-opacity))}.hover\:bg-gray-800:hover{--tw-bg-opacity:1;background-color:rgba(31,41,55,var(--tw-bg-opacity))}.hover\:bg-red-500:hover{--tw-bg-opacity:1;background-color:rgba(239,68,68,var(--tw-bg-opacity))}.bg-cover{background-size:cover}.border-black{--tw-border-opacity:1;border-color:rgba(0,0,0,var(--tw-border-opacity))}.border-white{--tw-border-opacity:1;border-color:rgba(255,255,255,var(--tw-border-opacity))}.border-gray-300{--tw-border-opacity:1;border-color:rgba(209,213,219,var(--tw-border-opacity))}.border-gray-400{--tw-border-opacity:1;border-color:rgba(156,163,175,var(--tw-border-opacity))}.border-red-500{--tw-border-opacity:1;border-color:rgba(239,68,68,var(--tw-border-opacity))}.hover\:border-white:hover{--tw-border-opacity:1;border-color:rgba(255,255,255,var(--tw-border-opacity))}.hover\:border-gray-400:hover{--tw-border-opacity:1;border-color:rgba(156,163,175,var(--tw-border-opacity))}.rounded-sm{border-radius:.125rem}.rounded{border-radius:.25rem}.rounded-md{border-radius:.375rem}.rounded-full{border-radius:9999px}.border-solid{border-style:solid}.border-dashed{border-style:dashed}.border{border-width:1px}.cursor-pointer{cursor:pointer}.cursor-not-allowed{cursor:not-allowed}.block{display:block}.inline-block{display:inline-block}.flex{display:flex}.table{display:table}.grid{display:grid}.hidden{display:none}.flex-row{flex-direction:row}.flex-col{flex-direction:column}.flex-wrap{flex-wrap:wrap}.items-start{align-items:flex-start}.items-center{align-items:center}.items-stretch{align-items:stretch}.self-start{align-self:flex-start}.self-stretch{align-self:stretch}.justify-start{justify-content:flex-start}.justify-end{justify-content:flex-end}.justify-center{justify-content:center}.justify-between{justify-content:space-between}.justify-self-end{justify-self:end}.flex-1{flex:1 1 0%}.font-light{font-weight:300}.font-normal{font-weight:400}.font-medium{font-weight:500}.font-semibold{font-weight:600}.font-bold{font-weight:700}.font-extrabold{font-weight:800}.h-0{height:0}.h-4{height:1rem}.h-5{height:1.25rem}.h-6{height:1.5rem}.h-48{height:12rem}.h-64{height:16rem}.h-96{height:24rem}.h-0\.5{height:.125rem}.h-full{height:100%}.text-xs{font-size:.75rem;line-height:1rem}.text-sm{font-size:.875rem;line-height:1.25rem}.text-xl{font-size:1.25rem;line-height:1.75rem}.text-2xl{font-size:1.5rem;line-height:2rem}.text-3xl{font-size:1.875rem;line-height:2.25rem}.m-auto{margin:auto}.mr-0{margin-right:0}.mb-0{margin-bottom:0}.mr-1{margin-right:.25rem}.mb-1{margin-bottom:.25rem}.ml-1{margin-left:.25rem}.mt-2{margin-top:.5rem}.mr-2{margin-right:.5rem}.mb-2{margin-bottom:.5rem}.ml-2{margin-left:.5rem}.mt-3{margin-top:.75rem}.mr-3{margin-right:.75rem}.mb-3{margin-bottom:.75rem}.ml-3{margin-left:.75rem}.mr-4{margin-right:1rem}.mb-4{margin-bottom:1rem}.ml-4{margin-left:1rem}.mr-5{margin-right:1.25rem}.ml-5{margin-left:1.25rem}.mt-6{margin-top:1.5rem}.mr-6{margin-right:1.5rem}.mb-6{margin-bottom:1.5rem}.mb-12{margin-bottom:3rem}.mt-16{margin-top:4rem}.max-w-md{max-width:28rem}.max-w-screen-xl{max-width:1280px}.overflow-hidden{overflow:hidden}.overflow-scroll{overflow:scroll}.p-6{padding:1.5rem}.p-8{padding:2rem}.py-1{padding-top:.25rem;padding-bottom:.25rem}.px-1{padding-left:.25rem;padding-right:.25rem}.py-2{padding-top:.5rem;padding-bottom:.5rem}.px-2{padding-left:.5rem;padding-right:.5rem}.py-3{padding-top:.75rem;padding-bottom:.75rem}.px-3{padding-left:.75rem;padding-right:.75rem}.px-4{padding-left:1rem;padding-right:1rem}.py-6{padding-top:1.5rem;padding-bottom:1.5rem}.px-6{padding-left:1.5rem;padding-right:1.5rem}.py-12{padding-top:3rem;padding-bottom:3rem}.pb-6{padding-bottom:1.5rem}.static{position:static}.absolute{position:absolute}.relative{position:relative}.inset-y-0{top:0;bottom:0}.left-0{left:0}.resize{resize:both}*{--tw-shadow:0 0 transparent}.shadow-sm{--tw-shadow:0 1px 2px 0 rgba(0,0,0,0.05)}.shadow,.shadow-sm{box-shadow:var(--tw-ring-offset-shadow,0 0 transparent),var(--tw-ring-shadow,0 0 transparent),var(--tw-shadow)}.shadow{--tw-shadow:0 1px 3px 0 rgba(0,0,0,0.1),0 1px 2px 0 rgba(0,0,0,0.06)}.shadow-md{--tw-shadow:0 4px 6px -1px rgba(0,0,0,0.1),0 2px 4px -1px rgba(0,0,0,0.06)}.shadow-inner,.shadow-md{box-shadow:var(--tw-ring-offset-shadow,0 0 transparent),var(--tw-ring-shadow,0 0 transparent),var(--tw-shadow)}.shadow-inner{--tw-shadow:inset 0 2px 4px 0 rgba(0,0,0,0.06)}.shadow-card{--tw-shadow:0 2px 1px -1px rgba(0,0,0,0.2),0 1px 1px 0 rgba(0,0,0,0.14),0 1px 3px 0 rgba(0,0,0,0.12);box-shadow:var(--tw-ring-offset-shadow,0 0 transparent),var(--tw-ring-shadow,0 0 transparent),var(--tw-shadow)}*{--tw-ring-inset:var(--tw-empty,/*!*/ /*!*/);--tw-ring-offset-width:0px;--tw-ring-offset-color:#fff;--tw-ring-color:rgba(59,130,246,0.5);--tw-ring-offset-shadow:0 0 transparent;--tw-ring-shadow:0 0 transparent}.text-center{text-align:center}.text-black{--tw-text-opacity:1;color:rgba(0,0,0,var(--tw-text-opacity))}.text-white{--tw-text-opacity:1;color:rgba(255,255,255,var(--tw-text-opacity))}.text-gray-400{--tw-text-opacity:1;color:rgba(156,163,175,var(--tw-text-opacity))}.text-gray-500{--tw-text-opacity:1;color:rgba(107,114,128,var(--tw-text-opacity))}.text-gray-700{--tw-text-opacity:1;color:rgba(55,65,81,var(--tw-text-opacity))}.text-red-500{--tw-text-opacity:1;color:rgba(239,68,68,var(--tw-text-opacity))}.text-red-600{--tw-text-opacity:1;color:rgba(220,38,38,var(--tw-text-opacity))}.text-blue-600{--tw-text-opacity:1;color:rgba(37,99,235,var(--tw-text-opacity))}.hover\:text-black:hover{--tw-text-opacity:1;color:rgba(0,0,0,var(--tw-text-opacity))}.hover\:text-white:hover{--tw-text-opacity:1;color:rgba(255,255,255,var(--tw-text-opacity))}.hover\:text-gray-500:hover{--tw-text-opacity:1;color:rgba(107,114,128,var(--tw-text-opacity))}.hover\:text-red-600:hover{--tw-text-opacity:1;color:rgba(220,38,38,var(--tw-text-opacity))}.uppercase{text-transform:uppercase}.underline{text-decoration:underline}.tracking-wider{letter-spacing:.05em}.tracking-widest{letter-spacing:.1em}.whitespace-nowrap{white-space:nowrap}.w-1{width:.25rem}.w-2{width:.5rem}.w-4{width:1rem}.w-5{width:1.25rem}.w-6{width:1.5rem}.w-10{width:2.5rem}.w-14{width:3.5rem}.w-16{width:4rem}.w-36{width:9rem}.w-64{width:16rem}.w-full{width:100%}.gap-12{gap:3rem}.grid-cols-1{grid-template-columns:repeat(1,minmax(0,1fr))}.transform{--tw-translate-x:0;--tw-translate-y:0;--tw-rotate:0;--tw-skew-x:0;--tw-skew-y:0;--tw-scale-x:1;--tw-scale-y:1;transform:translateX(var(--tw-translate-x)) translateY(var(--tw-translate-y)) rotate(var(--tw-rotate)) skewX(var(--tw-skew-x)) skewY(var(--tw-skew-y)) scaleX(var(--tw-scale-x)) scaleY(var(--tw-scale-y))}.hover\:scale-105:hover{--tw-scale-x:1.05;--tw-scale-y:1.05}.hover\:-translate-y-1:hover{--tw-translate-y:-0.25rem}.transition{transition-property:background-color,border-color,color,fill,stroke,opacity,box-shadow,transform,filter,-webkit-backdrop-filter;transition-property:background-color,border-color,color,fill,stroke,opacity,box-shadow,transform,filter,backdrop-filter;transition-property:background-color,border-color,color,fill,stroke,opacity,box-shadow,transform,filter,backdrop-filter,-webkit-backdrop-filter;transition-timing-function:cubic-bezier(.4,0,.2,1);transition-duration:.15s}.ease-in-out{transition-timing-function:cubic-bezier(.4,0,.2,1)}.duration-200{transition-duration:.2s}.duration-500{transition-duration:.5s}@-webkit-keyframes spin{to{transform:rotate(1turn)}}@keyframes spin{to{transform:rotate(1turn)}}@-webkit-keyframes ping{75%,to{transform:scale(2);opacity:0}}@keyframes ping{75%,to{transform:scale(2);opacity:0}}@-webkit-keyframes pulse{50%{opacity:.5}}@keyframes pulse{50%{opacity:.5}}@-webkit-keyframes bounce{0%,to{transform:translateY(-25%);-webkit-animation-timing-function:cubic-bezier(.8,0,1,1);animation-timing-function:cubic-bezier(.8,0,1,1)}50%{transform:none;-webkit-animation-timing-function:cubic-bezier(0,0,.2,1);animation-timing-function:cubic-bezier(0,0,.2,1)}}@keyframes bounce{0%,to{transform:translateY(-25%);-webkit-animation-timing-function:cubic-bezier(.8,0,1,1);animation-timing-function:cubic-bezier(.8,0,1,1)}50%{transform:none;-webkit-animation-timing-function:cubic-bezier(0,0,.2,1);animation-timing-function:cubic-bezier(0,0,.2,1)}}.filter{--tw-blur:var(--tw-empty,/*!*/ /*!*/);--tw-brightness:var(--tw-empty,/*!*/ /*!*/);--tw-contrast:var(--tw-empty,/*!*/ /*!*/);--tw-grayscale:var(--tw-empty,/*!*/ /*!*/);--tw-hue-rotate:var(--tw-empty,/*!*/ /*!*/);--tw-invert:var(--tw-empty,/*!*/ /*!*/);--tw-saturate:var(--tw-empty,/*!*/ /*!*/);--tw-sepia:var(--tw-empty,/*!*/ /*!*/);--tw-drop-shadow:var(--tw-empty,/*!*/ /*!*/);filter:var(--tw-blur) var(--tw-brightness) var(--tw-contrast) var(--tw-grayscale) var(--tw-hue-rotate) var(--tw-invert) var(--tw-saturate) var(--tw-sepia) var(--tw-drop-shadow)}.grayscale{--tw-grayscale:grayscale(100%)}@media (min-width:640px){.sm\:prose{color:#374151;max-width:65ch}.sm\:prose [class~=lead]{color:#4b5563;font-size:1.25em;line-height:1.6;margin-top:1.2em;margin-bottom:1.2em}.sm\:prose a{color:#dc2626;text-decoration:underline;font-weight:500}.sm\:prose a:hover{color:#ef4444}.sm\:prose strong{color:#111827;font-weight:600}.sm\:prose ol[type=A]{--list-counter-style:upper-alpha}.sm\:prose ol[type=a]{--list-counter-style:lower-alpha}.sm\:prose ol[type=I]{--list-counter-style:upper-roman}.sm\:prose ol[type=i]{--list-counter-style:lower-roman}.sm\:prose ol[type="1"]{--list-counter-style:decimal}.sm\:prose ol>li{position:relative;padding-left:1.75em}.sm\:prose ol>li:before{content:counter(list-item,var(--list-counter-style,decimal)) ".";position:absolute;font-weight:400;color:#6b7280;left:0}.sm\:prose ul>li{position:relative;padding-left:1.75em}.sm\:prose ul>li:before{content:"";position:absolute;background-color:#d1d5db;border-radius:50%;width:.375em;height:.375em;top:.6875em;left:.25em}.sm\:prose hr{border-color:#e5e7eb;border-top-width:1px;margin-top:3em;margin-bottom:3em}.sm\:prose blockquote{font-weight:500;font-style:italic;color:#111827;border-left-width:.25rem;border-left-color:#e5e7eb;quotes:"\201C""\201D""\2018""\2019";margin-top:1.6em;margin-bottom:1.6em;padding-left:1em}.sm\:prose blockquote p:first-of-type:before{content:open-quote}.sm\:prose blockquote p:last-of-type:after{content:close-quote}.sm\:prose h1{color:#111827;font-weight:800;font-size:2.25em;margin-top:0;margin-bottom:.8888889em;line-height:1.1111111}.sm\:prose h2{color:#111827;font-weight:700;font-size:1.5em;margin-top:2em;margin-bottom:1em;line-height:1.3333333}.sm\:prose h3{font-size:1.25em;margin-top:1.6em;margin-bottom:.6em;line-height:1.6}.sm\:prose h3,.sm\:prose h4{color:#111827;font-weight:600}.sm\:prose h4{margin-top:1.5em;margin-bottom:.5em;line-height:1.5}.sm\:prose figure figcaption{color:#6b7280;font-size:.875em;line-height:1.4285714;margin-top:.8571429em}.sm\:prose code{color:#111827;font-weight:600;font-size:.875em}.sm\:prose code:after,.sm\:prose code:before{content:"`"}.sm\:prose a code{color:#111827}.sm\:prose pre{color:#e5e7eb;background-color:#1f2937;overflow-x:auto;font-size:.875em;line-height:1.7142857;margin-top:1.7142857em;margin-bottom:1.7142857em;border-radius:.375rem;padding:.8571429em 1.1428571em}.sm\:prose pre code{background-color:transparent;border-width:0;border-radius:0;padding:0;font-weight:400;color:inherit;font-size:inherit;font-family:inherit;line-height:inherit}.sm\:prose pre code:after,.sm\:prose pre code:before{content:none}.sm\:prose table{width:100%;table-layout:auto;text-align:left;margin-top:2em;margin-bottom:2em;font-size:.875em;line-height:1.7142857}.sm\:prose thead{color:#111827;font-weight:600;border-bottom-width:1px;border-bottom-color:#d1d5db}.sm\:prose thead th{vertical-align:bottom;padding-right:.5714286em;padding-bottom:.5714286em;padding-left:.5714286em}.sm\:prose tbody tr{border-bottom-width:1px;border-bottom-color:#e5e7eb}.sm\:prose tbody tr:last-child{border-bottom-width:0}.sm\:prose tbody td{vertical-align:top;padding:.5714286em}.sm\:prose{font-size:1rem;line-height:1.75}.sm\:prose p{margin-top:1.25em;margin-bottom:1.25em}.sm\:prose figure,.sm\:prose img,.sm\:prose video{margin-top:2em;margin-bottom:2em}.sm\:prose figure>*{margin-top:0;margin-bottom:0}.sm\:prose h2 code{font-size:.875em}.sm\:prose h3 code{font-size:.9em}.sm\:prose ol,.sm\:prose ul{margin-top:1.25em;margin-bottom:1.25em}.sm\:prose li{margin-top:.5em;margin-bottom:.5em}.sm\:prose>ul>li p{margin-top:.75em;margin-bottom:.75em}.sm\:prose>ul>li>:first-child{margin-top:1.25em}.sm\:prose>ul>li>:last-child{margin-bottom:1.25em}.sm\:prose>ol>li>:first-child{margin-top:1.25em}.sm\:prose>ol>li>:last-child{margin-bottom:1.25em}.sm\:prose ol ol,.sm\:prose ol ul,.sm\:prose ul ol,.sm\:prose ul ul{margin-top:.75em;margin-bottom:.75em}.sm\:prose h2+*,.sm\:prose h3+*,.sm\:prose h4+*,.sm\:prose hr+*{margin-top:0}.sm\:prose thead th:first-child{padding-left:0}.sm\:prose thead th:last-child{padding-right:0}.sm\:prose tbody td:first-child{padding-left:0}.sm\:prose tbody td:last-child{padding-right:0}.sm\:prose>:first-child{margin-top:0}.sm\:prose>:last-child{margin-bottom:0}.sm\:flex{display:flex}.sm\:flex-row{flex-direction:row}.sm\:items-start{align-items:flex-start}.sm\:items-center{align-items:center}.sm\:flex-1{flex:1 1 0%}.sm\:h-auto{height:auto}.sm\:mb-0{margin-bottom:0}.sm\:mr-6{margin-right:1.5rem}.sm\:px-12{padding-left:3rem;padding-right:3rem}.sm\:text-left{text-align:left}.sm\:w-2\/5{width:40%}.sm\:w-3\/5{width:60%}.sm\:grid-cols-2{grid-template-columns:repeat(2,minmax(0,1fr))}}@media (min-width:1024px){.lg\:w-1\/4{width:25%}.lg\:w-3\/4{width:75%}.lg\:grid-cols-3{grid-template-columns:repeat(3,minmax(0,1fr))}}code[class*=language-],pre[class*=language-]{color:#f8f8f2;background:none;text-shadow:0 1px rgba(0,0,0,.3);font-family:Consolas,Monaco,Andale Mono,Ubuntu Mono,monospace;font-size:1em;text-align:left;white-space:pre;word-spacing:normal;word-break:normal;word-wrap:normal;line-height:1.5;-moz-tab-size:4;-o-tab-size:4;tab-size:4;-webkit-hyphens:none;-ms-hyphens:none;hyphens:none}pre[class*=language-]{padding:1em;margin:.5em 0;overflow:auto;border-radius:.3em}:not(pre)>code[class*=language-],pre[class*=language-]{background:#272822}:not(pre)>code[class*=language-]{padding:.1em;border-radius:.3em;white-space:normal}.token.cdata,.token.comment,.token.doctype,.token.prolog{color:#8292a2}.token.punctuation{color:#f8f8f2}.token.namespace{opacity:.7}.token.constant,.token.deleted,.token.property,.token.symbol,.token.tag{color:#f92672}.token.boolean,.token.number{color:#ae81ff}.token.attr-name,.token.builtin,.token.char,.token.inserted,.token.selector,.token.string{color:#a6e22e}.language-css .token.string,.style .token.string,.token.entity,.token.operator,.token.url,.token.variable{color:#f8f8f2}.token.atrule,.token.attr-value,.token.class-name,.token.function{color:#e6db74}.token.keyword{color:#66d9ef}.token.important,.token.regex{color:#fd971f}.token.bold,.token.important{font-weight:700}.token.italic{font-style:italic}.token.entity{cursor:help}</style><meta name="generator" content="Gatsby 3.4.0"/><title data-react-helmet="true">Dynamic Programming vs Divide-and-Conquer | Trekhleb</title><meta data-react-helmet="true" name="description" content="In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples - binary search and minimum edit distance (Levenshtein distance)"/><meta data-react-helmet="true" name="image" content="https://trekhleb.dev/static/2207cb6352250f4c7593b87071c55705/62b78/01-cover.png"/><meta data-react-helmet="true" property="og:title" content="Dynamic Programming vs Divide-and-Conquer | Trekhleb"/><meta data-react-helmet="true" property="og:description" content="In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples - binary search and minimum edit distance (Levenshtein distance)"/><meta data-react-helmet="true" property="og:url" content="https://trekhleb.dev/blog/2018/dynamic-programming-vs-divide-and-conquer/"/><meta data-react-helmet="true" property="og:image" content="https://trekhleb.dev/static/2207cb6352250f4c7593b87071c55705/62b78/01-cover.png"/><meta data-react-helmet="true" property="og:type" content="article"/><meta data-react-helmet="true" name="twitter:card" content="summary_large_image"/><meta data-react-helmet="true" name="twitter:creator" content="@Trekhleb"/><meta data-react-helmet="true" name="twitter:title" content="Dynamic Programming vs Divide-and-Conquer | Trekhleb"/><meta data-react-helmet="true" name="twitter:description" content="In this article I’m trying to explain the difference/similarities between dynamic programing and divide and conquer approaches based on two examples - binary search and minimum edit distance (Levenshtein distance)"/><meta data-react-helmet="true" name="twitter:image" content="https://trekhleb.dev/static/2207cb6352250f4c7593b87071c55705/62b78/01-cover.png"/><meta data-react-helmet="true" name="twitter:url" content="https://trekhleb.dev/blog/2018/dynamic-programming-vs-divide-and-conquer/"/><link rel="preconnect dns-prefetch" href="https://www.google-analytics.com"/><link rel="alternate" type="application/rss+xml" title="Trekhleb.dev RSS Feed" href="/rss.xml"/><link as="script" rel="preload" href="/webpack-runtime-6451c7fe678794e00b4b.js"/><link as="script" rel="preload" href="/framework-d63adeb7e1b44b7b8aa5.js"/><link as="script" rel="preload" href="/app-2e0826ec06cafce3bdee.js"/><link as="script" rel="preload" href="/commons-213c962999d4e181c8a0.js"/><link as="script" rel="preload" href="/component---src-templates-post-tsx-c4045391b1a7c095d609.js"/><link as="fetch" rel="preload" href="/page-data/blog/2018/dynamic-programming-vs-divide-and-conquer/page-data.json" crossorigin="anonymous"/><link as="fetch" rel="preload" href="/page-data/app-data.json" crossorigin="anonymous"/></head><body><div id="___gatsby"><div style="outline:none" tabindex="-1" id="gatsby-focus-wrapper"><main class="flex flex-col items-center"><div class="max-w-screen-xl self-stretch m-auto w-full"><header class="flex flex-row items-center px-6 sm:px-12 py-6"><div class="mr-6"><div><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 font-extrabold text-sm tracking-widest uppercase" href="/">Trekhleb</a></div></div><nav><ul class="flex flex-row"><li class="ml-5"><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 uppercase text-xs" href="/">About</a></li><li class="ml-5"><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 uppercase text-xs" href="/projects/">Projects</a></li><li class="ml-5"><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 uppercase text-xs" href="/blog/">Blog</a></li></ul></nav></header><article class="px-6 sm:px-12 py-6"><div class="flex flex-col items-center"><article class="w-full prose prose-sm sm:prose overflow-hidden prose-red" style="max-width:860px"><h1 class="text-3xl mb-6 uppercase font-extrabold ">Dynamic Programming vs Divide-and-Conquer</h1><div class="flex flex-row items-center "><div class="flex flex-row items-center mr-6"><svg stroke="currentColor" fill="none" stroke-width="2" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" class="mr-1" height="1em" width="1em" xmlns="http://www.w3.org/2000/svg"><rect x="3" y="4" width="18" height="18" rx="2" ry="2"></rect><line x1="16" y1="2" x2="16" y2="6"></line><line x1="8" y1="2" x2="8" y2="6"></line><line x1="3" y1="10" x2="21" y2="10"></line></svg>15 June, 2018</div><div class="flex flex-row items-center "><svg stroke="currentColor" fill="none" stroke-width="2" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" class="mr-1" height="1em" width="1em" xmlns="http://www.w3.org/2000/svg"><circle cx="12" cy="12" r="10"></circle><polyline points="12 6 12 12 16 14"></polyline></svg>7<!-- --> min to read</div></div><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:880px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:16.400000000000002%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAADCAIAAAAcOLh5AAAACXBIWXMAAAsTAAALEwEAmpwYAAAAgElEQVQI12NQ80hWdE2Qd4mXc45X90zW9ExRdE2Qc47X8kqRcoxVdU/CIZsq6RjDoOyWqOCSoOiaoOqRpOASL+kQI+ccp+6ZrOeTJu8Sj0dWwSWewcg/U9w+WsMzRdg2UtEtQcoxRswuSsUtyTI4R845Ts83XcIBi6xVSI6UYwwAtwgu0AyOKLMAAAAASUVORK5CYII=');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Dynamic Programming vs Divide-and-Conquer" title="Dynamic Programming vs Divide-and-Conquer" src="/static/2207cb6352250f4c7593b87071c55705/9c177/09.png" srcSet="/static/2207cb6352250f4c7593b87071c55705/63868/09.png 250w,/static/2207cb6352250f4c7593b87071c55705/0b533/09.png 500w,/static/2207cb6352250f4c7593b87071c55705/9c177/09.png 880w" sizes="(max-width: 880px) 100vw, 880px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><h2 id="tldr" style="position:relative">TL;DR<a href="#tldr" aria-label="tldr permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>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">binary search</a> and <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance">minimum edit distance</a> (Levenshtein distance).</p><blockquote><p>Also, in the <a href="https://trekhleb.dev/blog/2021/content-aware-image-resizing-in-javascript/">Content-aware image resizing in JavaScript</a> article I went through another powerful but yet simple example of dynamic programming for the Seam Carving algorithm. You might want to check it out as well. </p></blockquote><h2 id="the-problem" style="position:relative">The Problem<a href="#the-problem" aria-label="the problem permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>When I <a href="https://github.com/trekhleb/javascript-algorithms">started to learn algorithms</a> it was hard for me to understand the main idea of dynamic programming (<strong>DP</strong>) and how it is different from divide-and-conquer (<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">example</a>. But when we’re trying to solve the <strong>same</strong> problem using both DP and DC approaches to explain each of them, it feels for me like we may <strong>lose valuable detail</strong> that might help to catch the difference faster. These detail tells us that each technique serves best for <strong>different</strong> types of problems.</p><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><h2 id="dynamic-programming-and-divide-and-conquer-similarities" style="position:relative">Dynamic Programming and Divide-and-Conquer Similarities<a href="#dynamic-programming-and-divide-and-conquer-similarities" aria-label="dynamic programming and divide and conquer similarities permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>As I see it for now I can say that <strong>dynamic programming is an extension of the divide and conquer paradigm</strong>.</p><p>I would <strong>not</strong> treat them as something completely different. Because <strong>they 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>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>only if the problem has certain restrictions or prerequisites</strong>. After that dynamic programming extends divide and conquer approach with <strong>memoization</strong> or <strong>tabulation</strong> technique.</p><p>Let’s go step by step...</p><h2 id="dynamic-programming-prerequisitesrestrictions" style="position:relative">Dynamic Programming Prerequisites/Restrictions<a href="#dynamic-programming-prerequisitesrestrictions" aria-label="dynamic programming prerequisitesrestrictions permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>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><ul><li><a href="https://en.wikipedia.org/wiki/Optimal_substructure">Optimal substructure</a> - optimal solution can be constructed from optimal solutions of its sub-problems</li><li><a href="https://en.wikipedia.org/wiki/Overlapping_subproblems">Overlapping sub-problems</a> - problem can be broken down into sub-problems which are reused several times, or a recursive algorithm for the problem solves the same sub-problem over and over rather than always generating new sub-problems</li></ul><p>Once these two conditions are met we can say that this divide and conquer problem may be solved using dynamic programming approach.</p><h2 id="dynamic-programming-extension-for-divide-and-conquer" style="position:relative">Dynamic Programming Extension for Divide and Conquer<a href="#dynamic-programming-extension-for-divide-and-conquer" aria-label="dynamic programming extension for divide and conquer permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>Dynamic programming approach extends divide and conquer approach with two techniques (<strong>memoization</strong> and <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="language-text">O(2^n)</code> where DP solution doing the same with only <code class="language-text">O(n)</code> time.</p><p><strong>Memoization (top-down cache filling)</strong> refers to the technique of caching and reusing previously computed results. The memoized <code class="language-text">fib</code> function would thus look like this:</p><div class="gatsby-highlight" data-language="text"><pre class="language-text"><code class="language-text">memFib(n) {
if (mem[n] is undefined)
if (n < 2) result = n
else result = memFib(n-2) + memFib(n-1)
mem[n] = result
return mem[n]
}</code></pre></div><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="language-text">fib</code> would look like this:</p><div class="gatsby-highlight" data-language="text"><pre class="language-text"><code class="language-text">tabFib(n) {
mem[0] = 0
mem[1] = 1
for i = 2...n
mem[i] = mem[i-2] + mem[i-1]
return mem[n]
}</code></pre></div><p>You may read more about memoization and tabulation comparison <a href="https://programming.guide/dynamic-programming-vs-memoization-vs-tabulation.html">here</a>.</p><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><h2 id="so-what-the-difference-between-dp-and-dc-after-all" style="position:relative">So What the Difference Between DP and DC After All<a href="#so-what-the-difference-between-dp-and-dc-after-all" aria-label="so what the difference between dp and dc after all permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>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><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:48%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAKCAIAAAA7N+mxAAAACXBIWXMAAAsTAAALEwEAmpwYAAABsklEQVQoz3VRQW7aQBS1YMWOE/gE6YIlF0hv4KtwBy5Qdsmm6rJVu2olaNWQJlRp4hYXHJHENlCDi8dhhmDPjGf+r4xpFSnq0+gv/ryn9/S+EccxIaScSZIQQoQQ8i/EEzzeG5PJxHVdz/Ns2x6Px6PRSEqBCAAaQOMT6B0QkXNucM4ppfgflDwAWN+vl4slXe+ZAFCIEdF13U6nMxgMdmwQGUmpv6WezFalD2gglNzMb659dxoFEY1ELgqx4zimaVYqlWq1enx8hIihf2J/6Vz2X6zmJ1oXJqjR++19uHz/rv/2zefXZ9endEulkEar1TIMw7Is0zSfHRxQxnL5MA+cwBtKwRCx2+tGUcQlj+9Xd9Pb2WJGKFFKFc7tdtswjGazWa/Xnx8eSqn4w69FcB76Z2I7B8AwDHnGWcqCOPg2unBuh7NkuklZ0TZjzLKsWq3WaDRs+woRk+XF3fCl//MVW31VGorYiGESfvzR+/S917vqnrr9mMVFbERUSoVhmKbprkbMJefZhvONEFnRFoDWWkpJGWUbVs59bCnlv3sopcp2AXD39rbFr4bHJ8zzQvwH8jcNCHX8PS4AAAAASUVORK5CYII=');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Dynamic programming and divide and conquer paradigms dependency" title="Dynamic programming and divide and conquer paradigms dependency" src="/static/5a8f370f01f0db44fff93ee8aeba3f6c/00d43/02-dp.png" srcSet="/static/5a8f370f01f0db44fff93ee8aeba3f6c/63868/02-dp.png 250w,/static/5a8f370f01f0db44fff93ee8aeba3f6c/0b533/02-dp.png 500w,/static/5a8f370f01f0db44fff93ee8aeba3f6c/00d43/02-dp.png 1000w,/static/5a8f370f01f0db44fff93ee8aeba3f6c/aa440/02-dp.png 1500w,/static/5a8f370f01f0db44fff93ee8aeba3f6c/e8950/02-dp.png 2000w,/static/5a8f370f01f0db44fff93ee8aeba3f6c/9d6a9/02-dp.png 2256w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Dynamic programming and divide and conquer paradigms dependency</i></center><p>Let’s go and try to solve some problems using DP and DC approaches to make this illustration more clear.</p><h2 id="divide-and-conquer-example-binary-search" style="position:relative">Divide and Conquer Example: Binary Search<a href="#divide-and-conquer-example-binary-search" aria-label="divide and conquer example binary search permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p><a href="https://en.wikipedia.org/wiki/Binary_search_algorithm">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><h3 id="example" style="position:relative">Example<a href="#example" aria-label="example permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><p>Here is a visualization of the binary search algorithm where 4 is the target value.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:93.60000000000001%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAATCAIAAAAf7rriAAAACXBIWXMAAAsTAAALEwEAmpwYAAABcUlEQVQ4y52TwY7CIBCGuz6f8TGM7+F938hNPJqsFy/GtGprQgtiYQqlVAt0o2Rr1mS1uz8JAYaPgZkhaH+X1tpa+2RD8MQmhGia5s+wc65tW0KIUuo17JwTP1WWZRzHlFJ/0DO4rmsppXPOfssYUxRFXde94KqqHmzW2ifkHdZal2X5YGua5gXszZxzhFB3bb9ojOnlGWOMEGKMSSmFEIwxY0zfa/sIdUkSQlwuF3dTL9gX039g/9rroHXW2SRJiqLozurl2bUuV/mJnxBCGc78el/YOltUV4fGXuPcN9pdVXHJPeanHewHD/39ze2tKaO62nqdKp9YzrnWevYxm75Pl5/L8/nMGOOcA4D/JABQVRUAKKX85jzPA0IIpdT3o9Fo8DYYj8ecc4xxmqYAkCRJGIYAsFqt0jRdr9dhGGKM5/N5kN50OBwopcPhMAiCyWQipdzv94QQxth2u93tdlmWRVEUx3EURZvN5ng8LhaLLwNnSRW3MQ7kAAAAAElFTkSuQmCC');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Binary search algorithm logic" title="Binary search algorithm logic" src="/static/a3f8456289058a7401640fdf368e7c44/00d43/03-binary-search.png" srcSet="/static/a3f8456289058a7401640fdf368e7c44/63868/03-binary-search.png 250w,/static/a3f8456289058a7401640fdf368e7c44/0b533/03-binary-search.png 500w,/static/a3f8456289058a7401640fdf368e7c44/00d43/03-binary-search.png 1000w,/static/a3f8456289058a7401640fdf368e7c44/eb4a1/03-binary-search.png 1083w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Binary search algorithm logic</i></center><p>Let’s draw the same logic but in form of decision tree.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:64.4%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAANCAIAAAAmMtkJAAAACXBIWXMAAAsTAAALEwEAmpwYAAAB1UlEQVQoz22Ssa45QRTGJ1FdT+At9FqJRqJTaL0CicrS6UT0vIFobCPoVAoJjRDsZm2yy+6Y3bFr1po9N39z70b876+bzPedc745g6IoAgCMsWmamqadTidVVTHG7XYbISTLsmVZm81GUZTD4bDb7TDGACBcCF54nue6Lsb4er0SQnzfl2W5VCqt12vf903TxBhbLzzPg19+zJzzIAiiKHo+n6JQGIYAcHvx/IVzDm+g94Nw3m63WBSGoeu6jDEx5wcoDMMgCBaLRbfbVRQlbhUrHo8HpbTf7w+HQ8YYIYRS+pPZ933GmCRJX19fy+XSsqzj8cgYi1/FcRzTNNPpdC6Xs217v9+rqiqqoyiKGGOr1WoymRiGwRgLgkAEjvE8bzabzedzQsj9fo/DI9u2L5cLpZRzTggxDMP3/eiFcNq2rWkaYywMQ4yxruuUUjEXSiQSvV5PZAOATCaTz+fP57NQbLfbVCrV6XQAIAgCAMhms4VCQdM0jDEqFovT6VRsCwBqtVq9XnddV5h1XS+Xy6PRSOwCABqNRrPZxBgTQtD/C6CUvv+EPwWO4/zLzDl/36EoPxgMJEkSzf8UjMfjarX62VncVSqVZDKpKEoc50PQarUQQt9EcLPYNJUqCAAAAABJRU5ErkJggg==');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Binary search algorithm decision tree" title="Binary search algorithm decision tree" src="/static/a9f79d904494ff947b2d730de4e9fbba/00d43/04-bs-decision-tree.png" srcSet="/static/a9f79d904494ff947b2d730de4e9fbba/63868/04-bs-decision-tree.png 250w,/static/a9f79d904494ff947b2d730de4e9fbba/0b533/04-bs-decision-tree.png 500w,/static/a9f79d904494ff947b2d730de4e9fbba/00d43/04-bs-decision-tree.png 1000w,/static/a9f79d904494ff947b2d730de4e9fbba/aa440/04-bs-decision-tree.png 1500w,/static/a9f79d904494ff947b2d730de4e9fbba/efeb1/04-bs-decision-tree.png 1593w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Binary search algorithm decision tree</i></center><p>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>Can we apply dynamic programming to it? <strong>No</strong>. It is because <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>must be</strong> overlapped somehow.</p><p>Normally every time you draw a decision tree and it is actually a <strong>tree</strong> (and <strong>not</strong> a decision <strong>graph</strong>) it would mean that you don’t have overlapping sub-problems and this is not dynamic programming problem.</p><h3 id="the-code" style="position:relative">The Code<a href="#the-code" aria-label="the code permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><p><a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/search/binary-search">Here</a> you may find complete source code of binary search function with test cases and explanations.</p><div class="gatsby-highlight" data-language="javascript"><pre class="language-javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span><span class="token parameter">sortedArray<span class="token punctuation">,</span> seekElement</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">let</span> startIndex <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">let</span> endIndex <span class="token operator">=</span> sortedArray<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>startIndex <span class="token operator"><=</span> endIndex<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">const</span> middleIndex <span class="token operator">=</span> startIndex <span class="token operator">+</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>endIndex <span class="token operator">-</span> startIndex<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token comment">// If we've found the element just return its position.</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>sortedArray<span class="token punctuation">[</span>middleIndex<span class="token punctuation">]</span> <span class="token operator">===</span> seekElement<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">return</span> middleIndex<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// Decide which half to choose: left or right one.</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>sortedArray<span class="token punctuation">[</span>middleIndex<span class="token punctuation">]</span> <span class="token operator"><</span> seekElement<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token comment">// Go to the right half of the array.</span>
startIndex <span class="token operator">=</span> middleIndex <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
<span class="token comment">// Go to the left half of the array.</span>
endIndex <span class="token operator">=</span> middleIndex <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span></code></pre></div><h2 id="dynamic-programming-example-minimum-edit-distance" style="position:relative">Dynamic Programming Example: Minimum Edit Distance<a href="#dynamic-programming-example-minimum-edit-distance" aria-label="dynamic programming example minimum edit distance permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>Normally when it comes to dynamic programming examples the <a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci">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><a href="https://en.wikipedia.org/wiki/Levenshtein_distance">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>insertions, deletions or substitutions</em>) required to change one word into the other.</p><h3 id="example-1" style="position:relative">Example<a href="#example-1" aria-label="example 1 permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><p>For 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><ul><li><strong>k</strong>itten → <strong>s</strong>itten (substitution of “s” for “k”)</li><li>sitt<strong>e</strong>n → sitt<strong>i</strong>n (substitution of “i” for “e”)</li><li>sittin → sittin<strong>g</strong> (insertion of “g” at the end).</li></ul><h3 id="applications" style="position:relative">Applications<a href="#applications" aria-label="applications permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><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><h3 id="mathematical-definition" style="position:relative">Mathematical Definition<a href="#mathematical-definition" aria-label="mathematical definition permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><p>Mathematically, the Levenshtein distance between two strings <code class="language-text">a</code>, <code class="language-text">b</code> (of length <code class="language-text">|a|</code> and <code class="language-text">|b|</code> respectively) is given by function <code class="language-text">lev(|a|, |b|)</code> where:</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:880px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:18.8%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAECAIAAAABPYjBAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAlUlEQVQI123OwaqEMAyFYd//IUUw2lgSEkxCaanthZG5q/k2Z/XDWeaXiBzHkXOOiPlLKQUAEFFEVLW1tsRHKQURI2LbtpSSqro7Ed33PcZ44967f9RaW2vP8yxEJCJmllJCxHVd930HAGYmImautb59RADAeZ7/15Z3xhgi0nu/rivnzMxm5u5mpqrM7O5zzufrjf8AJEjk9/OKpv4AAAAASUVORK5CYII=');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Mathematical definition" title="Mathematical definition" src="/static/6c784025b4cfbb2200fcdb61c335fcc3/9c177/05-levinshtein-formula.png" srcSet="/static/6c784025b4cfbb2200fcdb61c335fcc3/63868/05-levinshtein-formula.png 250w,/static/6c784025b4cfbb2200fcdb61c335fcc3/0b533/05-levinshtein-formula.png 500w,/static/6c784025b4cfbb2200fcdb61c335fcc3/9c177/05-levinshtein-formula.png 880w" sizes="(max-width: 880px) 100vw, 880px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><p>Note that the first element in the minimum corresponds to <strong>deletion</strong> (from <code class="language-text">a</code> to <code class="language-text">b</code>), the second to <strong>insertion</strong> and the third to <strong>match or mismatch</strong>, depending on whether the respective symbols are the same.</p><h3 id="explanation" style="position:relative">Explanation<a href="#explanation" aria-label="explanation permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><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>ME</strong> and <strong>MY</strong>. Intuitively you already know that minimum edit distance here is <strong>1</strong> operation and this operation is <em>“replace <strong>E</strong> with <strong>Y</strong>”</em>. 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>Saturday</strong> into <strong>Sunday</strong>.</p><p>To apply the formula to M<strong>E</strong>→M<strong>Y</strong> transformation we need to know minimum edit distances of ME→M, M→MY and M→M transformations in prior. Then we will need to pick the minimum one and add +1 operation to transform last letters E→Y.</p><p>So we can already see here a recursive nature of the solution: minimum edit distance of ME→MY transformation is being calculated based on three previously possible transformations. Thus we may say that this is <strong>divide and conquer algorithm</strong>.</p><p>To explain this further let’s draw the following matrix.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:36.8%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAHCAIAAACHqfpvAAAACXBIWXMAAAsTAAALEwEAmpwYAAABAElEQVQY042Q226EIBCGff9n61WbZpPGs+CuKMcREBBo1N1NL/tnLuaQb+bPFPmlbdtSSjHGfd/z/1T8LeZ5JoQIId6dlFIIwVqLx0NCiqv5hK/MOaekGjHGfb9MU3yNc0oRIAI4hI/oB98PUZt0riicczFGgPV2+2R9B2gAQjbnnmxOetfar4NqJn2/rwhBtwa4hodtSmnXtliMVVM9qkYL4bx/2zbWWGcnSggjVNCZL1xyADDGFOdZQAhhgdup/fj6Ln9KqeRFHrAx1m4LZZQyxjhjgjLOOFdKFSEE7z1llEgCBsqmrOv6+tnJ5tVncKll4aEiEmHgoee78cdTfgH4TpGh1kC/YQAAAABJRU5ErkJggg==');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Simple example of finding minimum edit distance between ME and MY strings" title="Simple example of finding minimum edit distance between ME and MY strings" src="/static/c5a8a82c328743201cb06fbb89786395/00d43/05-levinshtein-matrix.png" srcSet="/static/c5a8a82c328743201cb06fbb89786395/63868/05-levinshtein-matrix.png 250w,/static/c5a8a82c328743201cb06fbb89786395/0b533/05-levinshtein-matrix.png 500w,/static/c5a8a82c328743201cb06fbb89786395/00d43/05-levinshtein-matrix.png 1000w,/static/c5a8a82c328743201cb06fbb89786395/aa440/05-levinshtein-matrix.png 1500w,/static/c5a8a82c328743201cb06fbb89786395/4ed6a/05-levinshtein-matrix.png 1713w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Simple example of finding minimum edit distance between ME and MY strings</i></center><ul><li><strong>Cell (0,1)</strong> contains red number 1. It means that we need 1 operation to transform <strong>M</strong> to <strong>empty string</strong>: delete <strong>M</strong>. This is why this number is red.</li><li><strong>Cell (0,2)</strong> contains red number 2. It means that we need 2 operations to transform <strong>ME</strong> to <strong>empty string</strong>: delete <strong>E</strong>, delete <strong>M</strong>.</li><li><strong>Cell (1,0)</strong> contains green number 1. It means that we need 1 operation to transform empty string to <strong>M</strong>: insert <strong>M</strong>. This is why this number is green.</li><li><strong>Cell (2,0)</strong> contains green number 2. It means that we need 2 operations to transform empty string to <strong>MY</strong>: insert <strong>Y</strong>, insert <strong>M</strong>.</li><li><strong>Cell (1,1)</strong> contains number 0. It means that it costs nothing to transform <strong>M</strong> to <strong>M</strong>.</li><li><strong>Cell (1,2)</strong> contains red number 1. It means that we need 1 operation to transform <strong>ME</strong> to <strong>M</strong>: delete <strong>E</strong>.</li><li>And so on...</li></ul><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→Sunday transformation)?</p><p>The good news is that according to the formula you only need three adjacent cells <code class="language-text">(i-1, j)</code>, <code class="language-text">(i-1, j-1)</code>, and <code class="language-text">(i, j-1)</code> to calculate the number for current cell <code class="language-text">(i, j)</code> . 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="language-text">i</code>-s row and <code class="language-text">j</code>-s column</p><p>So, once again you may clearly see the recursive nature of the problem.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:30.8%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAGCAIAAABM9SnKAAAACXBIWXMAAAsTAAALEwEAmpwYAAAA20lEQVQY01WQy5GGIBCEDdYYPJmFSXj/TcAcDMGlBAEFHwgD9tbKrlX73aZrpqt7ipQSAM45Y8x7DyArWmvG2Hmer2KMmabJWgvgvm8ARUpp27ZlWZRS7+q+71LKeZ6ttXlvXVcppdbaGJOVn2POuRDi+COn4JwDqKqqrmsA4zh679+RiH6PlVJCiLIs27bNkpRSCOG9/3w+XdcByO7dQwghpRRjNMYURHRdV9M0fd/nMjHG67qcczHGnJCInHP04JwD4JwbhqHAf1JKx3GEEIjo6yF/Mfu+bXPsb4k/TjNnB8OoAAAAAElFTkSuQmCC');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Recursive nature of minimum edit distance problem" title="Recursive nature of minimum edit distance problem" src="/static/29a78dfa484fa4b257490df9e172ed74/00d43/06-recursive-nature.png" srcSet="/static/29a78dfa484fa4b257490df9e172ed74/63868/06-recursive-nature.png 250w,/static/29a78dfa484fa4b257490df9e172ed74/0b533/06-recursive-nature.png 500w,/static/29a78dfa484fa4b257490df9e172ed74/00d43/06-recursive-nature.png 1000w,/static/29a78dfa484fa4b257490df9e172ed74/aa440/06-recursive-nature.png 1500w,/static/29a78dfa484fa4b257490df9e172ed74/e8950/06-recursive-nature.png 2000w,/static/29a78dfa484fa4b257490df9e172ed74/52c1b/06-recursive-nature.png 2163w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Recursive nature of minimum edit distance problem</i></center><p>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>overlapping sub-problems</strong> and <strong>optimal substructure</strong> restrictions? <strong>Yes</strong>. Let’s see it from decision graph.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:29.599999999999998%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAGCAIAAABM9SnKAAAACXBIWXMAAAsTAAALEwEAmpwYAAAA3UlEQVQY022QwWrDMAyG8/5PNnpYdxnboYWxsiZxEteJY8mSLHk06WGDfhch+D9+pKb+oZTinGvbFhHrMzjPMbicaV+bfQDAOI67UzaGYYjr+s8UWfvDfH0BQDO7y2YqwjFG7z0iCnNGJGY/jcsyM7Oq7nLOOd4uYfpCvMtm1szdq7scIaUQAjPfuvfh+yCcQ/cWp89lWfq+F5Faq5kxEyIR0aOZcoIUASClpKpEkNagWtYYmKCUQkR7uapiOPfdz+l0ds557x83V7PN5Dh+rMMxpfj0YbbFSikiwsy/xq1bhTG3fg4AAAAASUVORK5CYII=');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Decision graph for minimum edit distance with overlapping sub-problems" title="Decision graph for minimum edit distance with overlapping sub-problems" src="/static/7ba6c9973834b50d2e70230d027fdc04/00d43/07-decision-graph.png" srcSet="/static/7ba6c9973834b50d2e70230d027fdc04/63868/07-decision-graph.png 250w,/static/7ba6c9973834b50d2e70230d027fdc04/0b533/07-decision-graph.png 500w,/static/7ba6c9973834b50d2e70230d027fdc04/00d43/07-decision-graph.png 1000w,/static/7ba6c9973834b50d2e70230d027fdc04/aa440/07-decision-graph.png 1500w,/static/7ba6c9973834b50d2e70230d027fdc04/e8950/07-decision-graph.png 2000w,/static/7ba6c9973834b50d2e70230d027fdc04/044a9/07-decision-graph.png 3036w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Decision graph for minimum edit distance with overlapping sub-problems</i></center><p>First, this is <strong>not</strong> a decision <strong>tree</strong>. It is a decision <strong>graph</strong>. You may see a number of <strong>overlapping sub-problems</strong> on the picture that are marked with red. Also, there is no way to reduce the number of operations and make it less than a minimum of those three adjacent cells from the formula.</p><p>Also, you may notice that each cell number in the matrix is being calculated based on previous ones. Thus, the <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>Applying these principles further we may solve more complicated cases like with Saturday→Sunday transformation.</p><p><span class="gatsby-resp-image-wrapper" style="position:relative;display:block;margin-left:auto;margin-right:auto;max-width:1000px">
<span class="gatsby-resp-image-background-image" style="padding-bottom:46.4%;position:relative;bottom:0;left:0;background-image:url('data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABQAAAAJCAIAAAC9o5sfAAAACXBIWXMAAAsTAAALEwEAmpwYAAABV0lEQVQoz3WR3Y7iMAxG+1a8M3c8BYKVFvaCoQWmi7oVTOy4CflxStukK9rRajTSHuUiFzm2vzhLKRljiIiaRmktpQQAKSURSSnv93sIYfwPWQhBABR5XhwO5zw/n88wobUmIgBg5jHGYRicc565b9voOaX0kh+PByIe396Kw+FSFOv1+nQ6EZGepkBEDmFs265tb7fbBwATJRBjip+d56dz4T9V9ePnr/L3NTDPzZlD3w3d8/mSxYdRD6Ocb2MfU2atRUQAICmbpkHE9/dys9nUdU1EQgjv/TCOQ4zWWu9d6Hrbjf4Z+yFlWus5JBEppQAAEfM83+12l8tFCPHKPI5zyO8f5r0XQsxO0zT/7tfrdbvdHo/HWf5Kms5LZmZElFIqpT53Ni2JmcuyXCwWy+UyxliWZV3X3wplfd8756y1bsJOGGP8xGq1qqrKWrvf740xMcav8l/bFfdOb0hwJwAAAABJRU5ErkJggg==');background-size:cover;display:block"></span>
<img class="gatsby-resp-image-image" alt="Minimum edit distance to convert Saturday to Sunday" title="Minimum edit distance to convert Saturday to Sunday" src="/static/4277d4ff947d22cc2c2e5b43c422b468/00d43/08-minimum-edit-distance.png" srcSet="/static/4277d4ff947d22cc2c2e5b43c422b468/63868/08-minimum-edit-distance.png 250w,/static/4277d4ff947d22cc2c2e5b43c422b468/0b533/08-minimum-edit-distance.png 500w,/static/4277d4ff947d22cc2c2e5b43c422b468/00d43/08-minimum-edit-distance.png 1000w,/static/4277d4ff947d22cc2c2e5b43c422b468/aa440/08-minimum-edit-distance.png 1500w,/static/4277d4ff947d22cc2c2e5b43c422b468/29007/08-minimum-edit-distance.png 1600w" sizes="(max-width: 1000px) 100vw, 1000px" style="width:100%;height:100%;margin:0;vertical-align:middle;position:absolute;top:0;left:0" loading="lazy"/>
</span></p><center><i>Minimum edit distance to convert Saturday to Sunday</i></center><h3 id="the-code-1" style="position:relative">The Code<a href="#the-code-1" aria-label="the code 1 permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h3><p><a href="https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/string/levenshtein-distance">Here</a> you may find complete source code of minimum edit distance function with test cases and explanations.</p><div class="gatsby-highlight" data-language="javascript"><pre class="language-javascript"><code class="language-javascript"><span class="token keyword">function</span> <span class="token function">levenshteinDistance</span><span class="token punctuation">(</span><span class="token parameter">a<span class="token punctuation">,</span> b</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">const</span> distanceMatrix <span class="token operator">=</span> <span class="token function">Array</span><span class="token punctuation">(</span>b<span class="token punctuation">.</span>length <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span>
<span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">)</span>
<span class="token punctuation">.</span><span class="token function">map</span><span class="token punctuation">(</span>
<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token function">Array</span><span class="token punctuation">(</span>a<span class="token punctuation">.</span>length <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">)</span>
<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> a<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
distanceMatrix<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><=</span> b<span class="token punctuation">.</span>length<span class="token punctuation">;</span> j <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
distanceMatrix<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> j<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator"><=</span> b<span class="token punctuation">.</span>length<span class="token punctuation">;</span> j <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> a<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i <span class="token operator">+=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">const</span> indicator <span class="token operator">=</span> a<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">===</span> b<span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">?</span> <span class="token number">0</span> <span class="token operator">:</span> <span class="token number">1</span><span class="token punctuation">;</span>
distanceMatrix<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>
distanceMatrix<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token comment">// deletion</span>
distanceMatrix<span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token comment">// insertion</span>
distanceMatrix<span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> indicator<span class="token punctuation">,</span> <span class="token comment">// substitution</span>
<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">return</span> distanceMatrix<span class="token punctuation">[</span>b<span class="token punctuation">.</span>length<span class="token punctuation">]</span><span class="token punctuation">[</span>a<span class="token punctuation">.</span>length<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span></code></pre></div><h2 id="conclusion" style="position:relative">Conclusion<a href="#conclusion" aria-label="conclusion permalink" class="gatsby-remark-autolink-header-anchor after"><svg aria-hidden="true" focusable="false" height="16" version="1.1" viewBox="0 0 16 16" width="16"><path fill-rule="evenodd" d="M4 9h1v1H4c-1.5 0-3-1.69-3-3.5S2.55 3 4 3h4c1.45 0 3 1.69 3 3.5 0 1.41-.91 2.72-2 3.25V8.59c.58-.45 1-1.27 1-2.09C10 5.22 8.98 4 8 4H4c-.98 0-2 1.22-2 2.5S3 9 4 9zm9-3h-1v1h1c1 0 2 1.22 2 2.5S13.98 12 13 12H9c-.98 0-2-1.22-2-2.5 0-.83.42-1.64 1-2.09V6.25c-1.09.53-2 1.84-2 3.25C6 11.31 7.55 13 9 13h4c1.45 0 3-1.69 3-3.5S14.5 6 13 6z"></path></svg></a></h2><p>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>I hope this article has not brought you more confusion but rather shed some light on these two important algorithmic concepts! :)</p><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">JavaScript Algorithms and Data Structures</a> repository.</p><p>Happy coding!</p></article></div><div class="flex flex-row justify-center items-center mt-16"><div class="max-w-md"><div class="bg-white rounded-md shadow-md p-8"><h1 class="text-grey-darkest uppercase font-bold text-xl mb-3">Subscribe to the Newsletter</h1><p class="text-sm mb-3">Get my latest posts and project updates by email</p><form action="https://dev.us1.list-manage.com/subscribe/post?u=7714f14ff32085c685da2cfaa&amp;id=53ffa81463" method="post" class="flex flex-col"><input type="text" placeholder="First Name" name="FNAME" class="border py-2 px-3 mb-3 rounded border-gray-300 border-solid appearance-none" required=""/><input type="email" placeholder="Email" name="EMAIL" class="border py-2 px-3 mb-3 rounded border-gray-300 border-solid appearance-none" required=""/><div class="hidden" aria-hidden="true"><input type="text" name="b_7714f14ff32085c685da2cfaa_53ffa81463" tabindex="-1"/></div><input type="submit" value="Subscribe" class="transition duration-200 ease-in-out bg-black text-white py-2 px-3 rounded shadow-sm cursor-pointer hover:bg-gray-800"/></form></div></div></div></article><footer class="px-6 sm:px-12 py-12"><div class="flex flex-col sm:flex-row items-center "><div style="flex:1" class="flex flex-row items-center mb-6 sm:mb-0"><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 text-xs mr-5" href="/subscribe"><svg stroke="currentColor" fill="currentColor" stroke-width="0" viewBox="0 0 1024 1024" height="20" width="20" xmlns="http://www.w3.org/2000/svg"><path d="M928 160H96c-17.7 0-32 14.3-32 32v640c0 17.7 14.3 32 32 32h832c17.7 0 32-14.3 32-32V192c0-17.7-14.3-32-32-32zm-40 110.8V792H136V270.8l-27.6-21.5 39.3-50.5 42.8 33.3h643.1l42.8-33.3 39.3 50.5-27.7 21.5zM833.6 232L512 482 190.4 232l-42.8-33.3-39.3 50.5 27.6 21.5 341.6 265.6a55.99 55.99 0 0 0 68.7 0L888 270.8l27.6-21.5-39.3-50.5-42.7 33.2z"></path></svg><span class="w-2"></span>Subscribe</a><a href="https://github.com/trekhleb/trekhleb.github.io/discussions" class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 text-xs mr-5"><svg stroke="currentColor" fill="none" stroke-width="2" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" height="20" width="20" xmlns="http://www.w3.org/2000/svg"><path d="M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37 0 0 0-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44 0 0 0 20 4.77 5.07 5.07 0 0 0 19.91 1S18.73.65 16 2.48a13.38 13.38 0 0 0-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07 0 0 0 5 4.77a5.44 5.44 0 0 0-1.5 3.78c0 5.42 3.3 6.61 6.44 7A3.37 3.37 0 0 0 9 18.13V22"></path></svg><span class="w-2"></span>Feedback</a><a class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 text-xs" href="/rss.xml"><svg stroke="currentColor" fill="none" stroke-width="2" viewBox="0 0 24 24" stroke-linecap="round" stroke-linejoin="round" height="20" width="20" xmlns="http://www.w3.org/2000/svg"><path d="M4 11a9 9 0 0 1 9 9"></path><path d="M4 4a16 16 0 0 1 16 16"></path><circle cx="5" cy="19" r="1"></circle></svg><span class="w-2"></span>RSS</a></div><div style="flex:1" class="flex flex-row items-center justify-center"><ul class="flex flex-row flex-wrap "><li class="flex flex-row items-center last:mr-0 mr-2 ml-2"><a href="https://www.linkedin.com/in/trekhleb/" class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 " title="Oleksii Trekhleb on LinkedIn"><svg stroke="currentColor" fill="currentColor" stroke-width="0" viewBox="0 0 448 512" class="w-5 h-5" height="1em" width="1em" xmlns="http://www.w3.org/2000/svg"><path d="M416 32H31.9C14.3 32 0 46.5 0 64.3v383.4C0 465.5 14.3 480 31.9 480H416c17.6 0 32-14.5 32-32.3V64.3c0-17.8-14.4-32.3-32-32.3zM135.4 416H69V202.2h66.5V416zm-33.2-243c-21.3 0-38.5-17.3-38.5-38.5S80.9 96 102.2 96c21.2 0 38.5 17.3 38.5 38.5 0 21.3-17.2 38.5-38.5 38.5zm282.1 243h-66.4V312c0-24.8-.5-56.7-34.5-56.7-34.6 0-39.9 27-39.9 54.9V416h-66.4V202.2h63.7v29.2h.9c8.9-16.8 30.6-34.5 62.9-34.5 67.2 0 79.7 44.3 79.7 101.9V416z"></path></svg></a></li><li class="flex flex-row items-center last:mr-0 mr-2 ml-2"><a href="https://github.com/trekhleb" class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 " title="Oleksii Trekhleb on GitHub"><svg stroke="currentColor" fill="currentColor" stroke-width="0" viewBox="0 0 496 512" class="w-5 h-5" height="1em" width="1em" xmlns="http://www.w3.org/2000/svg"><path d="M165.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6zm-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3zm44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9zM244.8 8C106.1 8 0 113.3 0 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C428.2 457.8 496 362.9 496 252 496 113.3 383.5 8 244.8 8zM97.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1zm-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7zm32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1zm-11.4-14.7c-1.6 1-1.6 3.6 0 5.9 1.6 2.3 4.3 3.3 5.6 2.3 1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2z"></path></svg></a></li><li class="flex flex-row items-center last:mr-0 mr-2 ml-2"><a href="https://twitter.com/Trekhleb" class="transition duration-200 ease-in-out flex flex-row items-center hover:text-red-600 " title="Oleksii Trekhleb on Twitter"><svg stroke="currentColor" fill="currentColor" stroke-width="0" viewBox="0 0 512 512" class="w-5 h-5" height="1em" width="1em" xmlns="http://www.w3.org/2000/svg"><path d="M459.37 151.716c.325 4.548.325 9.097.325 13.645 0 138.72-105.583 298.558-298.558 298.558-59.452 0-114.68-17.219-161.137-47.106 8.447.974 16.568 1.299 25.34 1.299 49.055 0 94.213-16.568 130.274-44.832-46.132-.975-84.792-31.188-98.112-72.772 6.498.974 12.995 1.624 19.818 1.624 9.421 0 18.843-1.3 27.614-3.573-48.081-9.747-84.143-51.98-84.143-102.985v-1.299c13.969 7.797 30.214 12.67 47.431 13.319-28.264-18.843-46.781-51.005-46.781-87.391 0-19.492 5.197-37.36 14.294-52.954 51.655 63.675 129.3 105.258 216.365 109.807-1.624-7.797-2.599-15.918-2.599-24.04 0-57.828 46.782-104.934 104.934-104.934 30.213 0 57.502 12.67 76.67 33.137 23.715-4.548 46.456-13.32 66.599-25.34-7.798 24.366-24.366 44.833-46.132 57.827 21.117-2.273 41.584-8.122 60.426-16.243-14.292 20.791-32.161 39.308-52.628 54.253z"></path></svg></a></li></ul></div><div style="flex:1" class="hidden sm:flex"> </div></div></footer></div></main></div><div id="gatsby-announcer" style="position:absolute;top:0;width:1px;height:1px;padding:0;overflow:hidden;clip:rect(0, 0, 0, 0);white-space:nowrap;border:0" aria-live="assertive" aria-atomic="true"></div></div><script async="" src="https://www.googletagmanager.com/gtag/js?id=G-YJ73BX984Z"></script><script>
if(true) {
window.dataLayer = window.dataLayer || [];
function gtag(){window.dataLayer && window.dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-YJ73BX984Z', {"send_page_view":false});
}
</script><script id="gatsby-script-loader">/*<![CDATA[*/window.pagePath="/blog/2018/dynamic-programming-vs-divide-and-conquer/";/*]]>*/</script><script id="gatsby-chunk-mapping">/*<![CDATA[*/window.___chunkMapping={"polyfill":["/polyfill-b7afeec9af34d175ba4b.js"],"app":["/app-2e0826ec06cafce3bdee.js"],"component---src-pages-404-tsx":["/component---src-pages-404-tsx-63f1eb2c9d9eccd00add.js"],"component---src-pages-blog-tsx":["/component---src-pages-blog-tsx-09e5ed745cd76684f8ac.js"],"component---src-pages-index-tsx":["/component---src-pages-index-tsx-700f213869b8e0037911.js"],"component---src-pages-projects-tsx":["/component---src-pages-projects-tsx-781dc12fd2babbe9fac0.js"],"component---src-pages-subscribe-confirm-index-tsx":["/component---src-pages-subscribe-confirm-index-tsx-7d43f1b2228f03a924f8.js"],"component---src-pages-subscribe-index-tsx":["/component---src-pages-subscribe-index-tsx-c02ecb9201e3fc4b2ce6.js"],"component---src-pages-subscribe-thanks-index-tsx":["/component---src-pages-subscribe-thanks-index-tsx-cec855950644a6361532.js"],"component---src-templates-post-tsx":["/component---src-templates-post-tsx-c4045391b1a7c095d609.js"],"component---src-templates-project-tsx":["/component---src-templates-project-tsx-d7e84ca35145045f8249.js"]};/*]]>*/</script><script src="/polyfill-b7afeec9af34d175ba4b.js" nomodule=""></script><script src="/component---src-templates-post-tsx-c4045391b1a7c095d609.js" async=""></script><script src="/commons-213c962999d4e181c8a0.js" async=""></script><script src="/app-2e0826ec06cafce3bdee.js" async=""></script><script src="/framework-d63adeb7e1b44b7b8aa5.js" async=""></script><script src="/webpack-runtime-6451c7fe678794e00b4b.js" async=""></script></body></html>