{"id":133,"date":"2025-01-03T16:44:01","date_gmt":"2025-01-03T12:44:01","guid":{"rendered":"https:\/\/abthoughts.com\/?p=133"},"modified":"2025-01-09T14:21:53","modified_gmt":"2025-01-09T10:21:53","slug":"dynamic-programming-1","status":"publish","type":"post","link":"https:\/\/abthoughts.com\/?p=133","title":{"rendered":"Dynamic programming (1)"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">What is dynamic programming?<\/h2>\n\n\n\n<p>Dynamic programming, an innovative algorithmic approach introduced by Richard Bellman in 1950, aims to make recursion smarter and more efficient. In standard recursion, we often solve the same subproblem multiple times when it appears repeatedly in the recursion tree, leading to redundant calculations. Dynamic programming tackles this inefficiency by ensuring that each subproblem is solved only once, even if it recurs throughout the recursion tree, dramatically improving performance.<br><\/p>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"wp-block-media-text is-stacked-on-mobile\"><figure class=\"wp-block-media-text__media\"><img loading=\"lazy\" decoding=\"async\" width=\"402\" height=\"227\" src=\"http:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg\" alt=\"\" class=\"wp-image-134 size-full\" srcset=\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg 402w, https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071-300x169.jpeg 300w\" sizes=\"auto, (max-width: 402px) 100vw, 402px\" \/><\/figure><div class=\"wp-block-media-text__content\">\n<p>Richard Bellman is an American mathematician who invented dynamic programming on 1950.<\/p>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">From where the name dynamic programming came from?<\/h2>\n\n\n\n<p>Today, the word \u201cprogramming\u201d refers to writing computer applications or programs, but back in 1950, it meant planning or scheduling. The term \u201cdynamic programming\u201d emerged because the method focuses on planning to avoid solving the same problem multiple times. In essence, dynamic programming is recursion without repetition of the work.<br><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Fibonacci Series Generation: Recursion vs. Dynamic Programming<\/strong><\/h2>\n\n\n\n<p>When using a recursive approach to calculate the Fibonacci sequence, we compute f(4), which depends on f(3) and f(2). Each of these further depends on the two preceding numbers in the sequence. This process continues until we reach the leaf nodes, or base cases, in the recursion tree. The resulting recursion tree, as shown in the image below, reveals a key inefficiency: f(2) is calculated twice, f(1) appears three times, and f(0) shows up twice. This redundancy highlights the problem dynamic programming aims to solve.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"637\" src=\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/image-1024x637.png\" alt=\"\" class=\"wp-image-141\" srcset=\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/image-1024x637.png 1024w, https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/image-300x186.png 300w, https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/image-768x477.png 768w, https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/image.png 1139w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>What is dynamic programming? Dynamic programming, an innovative algorithmic approach introduced by Richard Bellman in 1950, aims to<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-133","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v23.6 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Dynamic programming (1) - ABthoughts<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/abthoughts.com\/?p=133\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Dynamic programming (1) - ABthoughts\" \/>\n<meta property=\"og:description\" content=\"What is dynamic programming? Dynamic programming, an innovative algorithmic approach introduced by Richard Bellman in 1950, aims to\" \/>\n<meta property=\"og:url\" content=\"https:\/\/abthoughts.com\/?p=133\" \/>\n<meta property=\"og:site_name\" content=\"ABthoughts\" \/>\n<meta property=\"article:published_time\" content=\"2025-01-03T12:44:01+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-01-09T10:21:53+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg\" \/>\n\t<meta property=\"og:image:width\" content=\"402\" \/>\n\t<meta property=\"og:image:height\" content=\"227\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Abdelrahman Fathy Bassiouny\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Abdelrahman Fathy Bassiouny\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/abthoughts.com\/?p=133\",\"url\":\"https:\/\/abthoughts.com\/?p=133\",\"name\":\"Dynamic programming (1) - ABthoughts\",\"isPartOf\":{\"@id\":\"https:\/\/abthoughts.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/abthoughts.com\/?p=133#primaryimage\"},\"image\":{\"@id\":\"https:\/\/abthoughts.com\/?p=133#primaryimage\"},\"thumbnailUrl\":\"http:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg\",\"datePublished\":\"2025-01-03T12:44:01+00:00\",\"dateModified\":\"2025-01-09T10:21:53+00:00\",\"author\":{\"@id\":\"https:\/\/abthoughts.com\/#\/schema\/person\/2b4a7aed9d893435d974f7c1205df9e6\"},\"breadcrumb\":{\"@id\":\"https:\/\/abthoughts.com\/?p=133#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/abthoughts.com\/?p=133\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/abthoughts.com\/?p=133#primaryimage\",\"url\":\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg\",\"contentUrl\":\"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg\",\"width\":402,\"height\":227},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/abthoughts.com\/?p=133#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/abthoughts.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Dynamic programming (1)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/abthoughts.com\/#website\",\"url\":\"https:\/\/abthoughts.com\/\",\"name\":\"ABthoughts\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/abthoughts.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/abthoughts.com\/#\/schema\/person\/2b4a7aed9d893435d974f7c1205df9e6\",\"name\":\"Abdelrahman Fathy Bassiouny\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/abthoughts.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/bcf8cb261478ad1011536386498157a3d506f31ae253acdb83591046974c192f?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/bcf8cb261478ad1011536386498157a3d506f31ae253acdb83591046974c192f?s=96&d=mm&r=g\",\"caption\":\"Abdelrahman Fathy Bassiouny\"},\"sameAs\":[\"http:\/\/abthoughts.com\",\"https:\/\/www.linkedin.com\/in\/abdelrahman-fathy-43a14553\"],\"url\":\"https:\/\/abthoughts.com\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Dynamic programming (1) - ABthoughts","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/abthoughts.com\/?p=133","og_locale":"en_US","og_type":"article","og_title":"Dynamic programming (1) - ABthoughts","og_description":"What is dynamic programming? Dynamic programming, an innovative algorithmic approach introduced by Richard Bellman in 1950, aims to","og_url":"https:\/\/abthoughts.com\/?p=133","og_site_name":"ABthoughts","article_published_time":"2025-01-03T12:44:01+00:00","article_modified_time":"2025-01-09T10:21:53+00:00","og_image":[{"width":402,"height":227,"url":"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg","type":"image\/jpeg"}],"author":"Abdelrahman Fathy Bassiouny","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Abdelrahman Fathy Bassiouny","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/abthoughts.com\/?p=133","url":"https:\/\/abthoughts.com\/?p=133","name":"Dynamic programming (1) - ABthoughts","isPartOf":{"@id":"https:\/\/abthoughts.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/abthoughts.com\/?p=133#primaryimage"},"image":{"@id":"https:\/\/abthoughts.com\/?p=133#primaryimage"},"thumbnailUrl":"http:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg","datePublished":"2025-01-03T12:44:01+00:00","dateModified":"2025-01-09T10:21:53+00:00","author":{"@id":"https:\/\/abthoughts.com\/#\/schema\/person\/2b4a7aed9d893435d974f7c1205df9e6"},"breadcrumb":{"@id":"https:\/\/abthoughts.com\/?p=133#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/abthoughts.com\/?p=133"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/abthoughts.com\/?p=133#primaryimage","url":"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg","contentUrl":"https:\/\/abthoughts.com\/wp-content\/uploads\/2025\/01\/IMG_0071.jpeg","width":402,"height":227},{"@type":"BreadcrumbList","@id":"https:\/\/abthoughts.com\/?p=133#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/abthoughts.com\/"},{"@type":"ListItem","position":2,"name":"Dynamic programming (1)"}]},{"@type":"WebSite","@id":"https:\/\/abthoughts.com\/#website","url":"https:\/\/abthoughts.com\/","name":"ABthoughts","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/abthoughts.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/abthoughts.com\/#\/schema\/person\/2b4a7aed9d893435d974f7c1205df9e6","name":"Abdelrahman Fathy Bassiouny","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/abthoughts.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/bcf8cb261478ad1011536386498157a3d506f31ae253acdb83591046974c192f?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/bcf8cb261478ad1011536386498157a3d506f31ae253acdb83591046974c192f?s=96&d=mm&r=g","caption":"Abdelrahman Fathy Bassiouny"},"sameAs":["http:\/\/abthoughts.com","https:\/\/www.linkedin.com\/in\/abdelrahman-fathy-43a14553"],"url":"https:\/\/abthoughts.com\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/posts\/133","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/abthoughts.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=133"}],"version-history":[{"count":8,"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/posts\/133\/revisions"}],"predecessor-version":[{"id":148,"href":"https:\/\/abthoughts.com\/index.php?rest_route=\/wp\/v2\/posts\/133\/revisions\/148"}],"wp:attachment":[{"href":"https:\/\/abthoughts.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/abthoughts.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/abthoughts.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}