{"id":3350,"date":"2020-09-12T17:20:51","date_gmt":"2020-09-13T00:20:51","guid":{"rendered":"https:\/\/careerkarma.com\/blog\/?p=3350"},"modified":"2020-09-12T17:39:16","modified_gmt":"2020-09-13T00:39:16","slug":"dynamic-programming","status":"publish","type":"post","link":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/","title":{"rendered":"Dynamic Programming: An Introduction"},"content":{"rendered":"\n

In computer science<\/a> there are several ways that describe the approach to solving an algorithm. Greedy, Naive, Divide-and-Conquer are all ways to solve algorithms. One such way is called dynamic programming (DP). In this article, we\u2019ll take a look at what Dynamic Programming is, its characteristics, and the two main approaches to solving algorithms with DP.<\/p>\n\n\n\n

What Is Dynamic Programming?<\/h2>\n\n\n\n

The concept of dynamic programming was created to help improve the efficiency of brute-force or divide-and-conquer methods of solving algorithms.<\/p>\n\n\n\n

Say, for instance, we have a knapsack and it can only fit a certain amount of items in it. What combination of items will give us the maximum value? Or, suppose we have a knapsack that has a certain weight capacity. What combination of items of given weights will give us maximum value?<\/p>\n\n\n\n

With dynamic programming, we take the problem and break it down into smaller overlapping sub problems. These problems are solved and stored in a data structure. More often than not, this type of approach will result in an optimal solution for the prompt your technical interviewer<\/a> has given you. In the next few sections, we will take a look at three solution types: naive, top-down, and bottom-up.<\/p>\n\n\n\n

Naive Solutions<\/h2>\n\n\n\n

A naive solution is one that would be the first that comes to mind to a programmer. It may not be the most efficient, and it may not take advantage of some concepts. Yet, it is a simple solution that solves the problem. As a newer programmer, it is in your best interest to come up with naive solutions first and refactor to optimize it later.<\/p>\n\n\n\n

Top-Down Solutions<\/h2>\n\n\n\n

This is the first way to use dynamic programming in your solution. A top-down solution will take a naive solution that uses recursion and then add a technique called memoization to optimize it. Memoization acts like a sort of cache to store our sub-problems as we go so that the algorithm will run faster. Usually this occurs in the form of an object or a dictionary.<\/p>\n\n\n\n

Bottom-Up Solutions<\/h2>\n\n\n\n

Another type of dynamic programming solution that avoids recursion and tabulates from the beginning is called a bottom-up solution. This is a great way to go if you want to avoid using a lot of memory or prevent an accidental stack overflow.<\/p>\n\n\n\n

Let\u2019s take a look at two common problems in each of the approaches: Fibonacci and Longest Common Substring<\/a>.<\/p>\n\n\n\n

Fibonacci<\/h3>\n\n\n\n

The Fibonacci Sequence is a series of numbers where each number is the sum of the previous two numbers, starting from 0 and 1:<\/p>\n\n\n\n

Fn = 0, 1, 1, 2, 3, 5, 8, 13, 21...etc.\n0 + 1 = 1\n1 + 1 = 2\n1 + 2 = 3\n2 + 3 = 5\n3 + 5 = 8\n5 + 8 = 13\n8 + 13 = 21\n13 + 21 = 34...etc.<\/pre><\/div>\n\n\n\n
The Prompt<\/h3>\n\n\n\n
Given a number, n<\/em>, find the nth<\/sup><\/em> number in a Fibonacci sequence.<\/p>\n\n\n\n
Solution 1: Naive<\/h4>\n\n\n\n
A naive solution is one that a programmer may come up with when first looking at a problem. Remember that naive doesn\u2019t necessarily mean bad. A naive solution usually means the problem can be solved by using other methods that can create a more optimal or efficient solution. A naive solution is good<\/em> because it means you are on the right track.<\/p>\n\n\n\n
An example naive solution for Fibonacci looks like this:<\/p>\n\n\n\n
const fibNaive = (num) => {\n   if(num < 2) {\n       return num;\n   }\n \n   return fibNaive(num - 1) + fibNaive(num - 2);\n};<\/pre><\/div>\n\n\n\n
At the outset this looks fairly simple and straightforward. We are using recursion to solve this problem. Our base case returns the number if it is less than two. Otherwise, it uses recursion to get the nth<\/sup><\/code> number by adding each call to the stack until we hit the base case. Then it adds up all the calls together to get our result. Because we have two operations going n<\/code> times, this is what we call O(2n<\/sup>)<\/em> runtime. We measure how good a solution is by its Big O Notation<\/a>. This is not an efficient solution because of its runtime, and should be avoided at all costs.<\/p>\n\n\n\n
Solution 2: Dynamic Programming Approach #1 — Top-Down with Memoization<\/h4>\n\n\n\n
We can use the naive solution from above and add memoization to it to create a top-down solution to the problem. Memoization acts as a cache that stores the solutions to our sub-problems. Thus, we don\u2019t have to calculate the Fibonacci sequence from the beginning every time. Here\u2019s the code:<\/p>\n\n\n\n
const fibMemo = (num, memo = { 0: 0, 1: 1 }) => {\n   if(num < 2) {\n       return memo[num];\n   }\n \n   let result = fibMemo(num - 1, memo) + fibMemo(num - 2, memo);\n   if(!memo[num]) {\n       memo[num] = result;\n   }\n \n   return result;\n  \n}<\/pre><\/div>\n\n\n\n
The basic solution is the same here. But we\u2019ve changed it up by adding a dictionary that will hold our Fibonacci values as we go through the recursion. Every time n<\/code> changes, we\u2019ll add a value to the memo<\/code> object passed into the fibMemo<\/code> function.<\/p>\n\n\n\n
The base case is pretty much the same here. The difference is that we are starting with a default memo that has our first two Fibonacci numbers in it. This is instead of just returning the number passed in. We are assigning the variable result<\/em> to our Fibonacci equation that we used in the return of the naive solution.<\/p>\n\n\n\n
In the if statement<\/a>, we are checking to see if the key exists in memo — if it doesn\u2019t then we add it. We return the result just like we did in the naive solution.<\/p>\n\n\n\n
Ultimately, there are two differences with this solution. For one, we added a memo<\/code> object that remembers what we have figured out so far. And two, we added a conditional that checks to see if that key:value pair exists in the memo<\/code> object. If not, it adds it.<\/p>\n\n\n\n
This solution changes the time complexity from O(2n<\/sup>) to O(n)<\/em>.<\/p>\n\n\n\n
Solution 3: Dynamic Programming Approach #2 — Bottom-Up with Tabulation<\/h4>\n\n\n\n
This version of the solution uses iteration to solve the problem and tabulates the result as we go. We start with a JavaScript object<\/a> (or an array is perfectly acceptable here too) that will store our values. We use those values to tabulate up to our nth<\/sup><\/code> number.<\/p>\n\n\n\n
const fibTab = (num) => {\n   let fibDict = { 1:0, 2:1 };\n \n   for(let i = 3; i <= num; i++) {\n       if(!fibDict[i]){\n           fibDict[i] = fibDict[i - 1] + fibDict[i - 2];\n       }\n   }\n   return fibDict[num];\n}<\/pre><\/div>\n\n\n\n
Just like the memoized version, this version is O(n)<\/em> runtime because we iterate over every single number between 1<\/code>…n<\/code> in this scenario.<\/p>\n\n\n\n
Next, let\u2019s take a look at another common problem, called the Longest Common Substring.<\/p>\n\n\n\n
Longest Common Substring<\/h3>\n\n\n\n
The Prompt<\/h4>\n\n\n\n
If given two strings, find the length of the longest common substring.<\/p>\n\n\n\n
The longest common substring of \"ABABC\"<\/code> and \"CABAB\"<\/code> would be \"ABAB\"<\/code> with a length of 4 because we see \"ABAB\"<\/code> in both strings.<\/p>\n\n\n\n
Solution 1: Naive Solution<\/h4>\n\n\n\n
A naive solution would be to find all the substrings in one string. Then, you would see if the other string has the substring, starting with the longest.<\/p>\n\n\n\n
const naiveSub = (str1, str2) => {\n   \/\/find all the substrings.\n   substrs = [];\n   maxString = "";\n   otherString = "";\n   if(str1.length > str2.length) { \n       maxString = str1;\n       otherString = str2;\n   } else {\n       maxString = str2;\n       otherString = str1;\n   }\n \n   for(let i = 0; i < maxString.length - 1; i++) {\n       let str = "";\n       str += maxString[i];\n       for(let j = i + 1; j < maxString.length; j++) {\n           str += maxString[j];\n           substrs.push(str);\n       }\n   } \/\/ O(n) * O(n) === O(n^2)\n   \/\/have all substrings\n   \/\/see if other string has any of values from array in it.\n \n   let maxLength = 0;\n   let maxSubStr = "";\n \n   substrs.forEach(string => { \/\/ O(m)\n       if(new RegExp(string).test(otherString)) {\n           if(maxLength < string.length) {\n               maxLength = string.length;\n               maxSubStr = string;\n           }\n       }\n   });\n   return [ maxLength, maxSubStr ];\n} \/\/ O(n^2 + m) <== Big O Notation for Naive Solution\n \nconsole.log(naiveSub("ABABC", "CABAB"));<\/pre><\/div>\n\n\n\n
The time complexity of the naive solution takes into account the size of both the substring array and the strings. The nested for loop is O(n2<\/sup>)<\/em>, and the forEach loop<\/a> is O(m)<\/em>. This is because the length of the array may be a different length than the strings. Since the two main blocks of code are stacked, we add the time complexities together. The final Big O is O(n2<\/sup> + m)<\/em>. While a naive solution may not be the best solution, it works and will put you on track to find more efficient ones.<\/p>\n\n\n\n
Solution 2: Top-Down Solution with Recursion<\/h4>\n\n\n\n
In dynamic programming, a top-down solution keeps track of the max count of letters in the substring each time we make a recursive call:<\/p>\n\n\n\n
const topDown = (str1, str2, count = 0) => {\n  \n   let i = str1.length;\n   let j = str2.length;\n   \/\/if the strings don't exist, return 0\n   if(i === 0 || j === 0) {\n       return count;\n   }\n \n   if(str1[i - 1] === str2[j - 1]) { \/\/ if the chars are the same, up the count and shorten string by 1\n       count = topDown(str1.slice(0, i - 1), str2.slice(0, j - 1), count + 1);\n   }\n   count = Math.max(count, \/\/max between count and the other function\n       Math.max( \/\/ max between looking at shortening one word vs shortening the other word.\n       topDown(str1.slice(0,  i), str2.slice(0, j - 1), 0),\n       topDown(str1.slice(0, i - 1), str2.slice(0, j), 0)));\n \n   return count;\n}\n \nconsole.log(topDown('alphabetical', 'abcada'));<\/pre><\/div>\n\n\n\n
Time complexity for this solution is O(n + m)<\/em> to account for the sizes of the different strings.<\/p>\n\n\n\n
Solution 3: Bottom-Up Solution with Tabulation<\/h4>\n\n\n\n
The third solution to this problem involves using the bottom-up approach. In this approach, you would create a 2-D array\/matrix that will tabulate what the max length of the substring is. The first thing to do is to create an empty matrix using the lengths of the strings.<\/p>\n\n\n\n
const create2DArray = (A, B) => {\n   const table = [];\n \n   for (let i = 0; i <= A.length; i += 1) {\n       table.push([]);\n       for (let j = 0; j <= B.length; j += 1) {\n           table[i].push(0);\n       }\n   }\n   return table;\n};<\/pre><\/div>\n\n\n\n
If our strings are \"techcareer\"<\/code> and \"tech career\"<\/code> our empty table will look like:<\/p>\n\n\n\n
[\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],\n  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]\n]<\/pre><\/div>\n\n\n\n
The purpose of creating an empty matrix is to create space in memory to tabulate and keep track of our matching substring lengths. As we go through we\u2019ll keep track of the max value, so we can return it at the end of the function.<\/p>\n\n\n\n
const bottomUp = (A, B) => {\n   let table = create2DArray(A, B); \/\/ create the table\n   let max = 0; \/\/ initialize and declare max substring length to be 0\n   \/\/start i and j at 1 so we can compare characters to previous row and column\n   for (let i = 1; i < A.length + 1; i += 1) {\n       for (let j = 1; j < B.length + 1; j += 1) {\n           \/\/our initial row and column is set to 0\n           if (i === 0 || j === 0) {\n               table[i][j] = 0;\n           }\n           \/\/if our strings chars are the same in the prev place\n           else if (A[i - 1] === B[j - 1]) {\n               \/\/assign this spot in table to the table[i - 1][j - 1]'s value + 1\n               table[i][j] = table[i - 1][j - 1] + 1;\n               max = Math.max(max, table[i][j]); \/\/compare the max to the new value at table[i][j] and reassign to max\n           } else {\n               table[i][j] = 0; \/\/if the chars are not the same, it will reset count to 0. We still keep track of the max seen so far.\n           }\n       }\n   }\n   return max;\n};\nlet str1 = 'techcareer';\nlet str2 = 'tech career';\nconsole.log(bottomUp(str1, str2));<\/pre><\/div>\n\n\n\n
The time complexity of this solution is not the best, at O(n * m)<\/em>, where n and m consist of the different string sizes. Space complexity is O(n * m)<\/em>, as well.<\/p>\n\n\n\n
Conclusion<\/h2>\n\n\n\n
In this article, we defined Dynamic Programming and how we can use it to make our naive solutions to problems more efficient. Don\u2019t worry if Dynamic Programming doesn\u2019t immediately come to you the first time you attempt it. Practicing this approach will help you get to the next level when it comes to data structures and algorithms!<\/p>\n","protected":false},"excerpt":{"rendered":"In computer science there are several ways that describe the approach to solving an algorithm. Greedy, Naive, Divide-and-Conquer are all ways to solve algorithms. One such way is called dynamic programming (DP). In this article, we\u2019ll take a look at what Dynamic Programming is, its characteristics, and the two main approaches to solving algorithms with…","protected":false},"author":77,"featured_media":22552,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[18070],"tags":[],"class_list":{"0":"post-3350","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-software-engineering-skills"},"acf":{"post_sub_title":"","sprint_id":"","query_class":"Software Engineering","school_sft":"","parent_sft":"","school_privacy_policy":"","has_review":null,"is_sponser_post":"","is_guest_post":[]},"yoast_head":"\nDynamic Programming: An Introduction | Career Karma<\/title>\n<meta name=\"description\" content=\"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Dynamic Programming: An Introduction\" \/>\n<meta property=\"og:description\" content=\"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\" \/>\n<meta property=\"og:site_name\" content=\"Career Karma\" \/>\n<meta property=\"article:publisher\" content=\"http:\/\/facebook.com\/careerkarmaapp\" \/>\n<meta property=\"article:published_time\" content=\"2020-09-13T00:20:51+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-09-13T00:39:16+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"675\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Christina Kopecky\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@career_karma\" \/>\n<meta name=\"twitter:site\" content=\"@career_karma\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Christina Kopecky\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\"},\"author\":{\"name\":\"Christina Kopecky\",\"@id\":\"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e\"},\"headline\":\"Dynamic Programming: An Introduction\",\"datePublished\":\"2020-09-13T00:20:51+00:00\",\"dateModified\":\"2020-09-13T00:39:16+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\"},\"wordCount\":1383,\"commentCount\":0,\"image\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg\",\"articleSection\":[\"Software Engineering\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\",\"url\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\",\"name\":\"Dynamic Programming: An Introduction | Career Karma\",\"isPartOf\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg\",\"datePublished\":\"2020-09-13T00:20:51+00:00\",\"dateModified\":\"2020-09-13T00:39:16+00:00\",\"author\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e\"},\"description\":\"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.\",\"breadcrumb\":{\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage\",\"url\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg\",\"contentUrl\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg\",\"width\":1200,\"height\":675,\"caption\":\"Dynamic Programming (with a Fibonacci spiral)\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Blog\",\"item\":\"https:\/\/careerkarma.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Software Engineering\",\"item\":\"https:\/\/careerkarma.com\/blog\/software-engineering-skills\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Dynamic Programming: An Introduction\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/careerkarma.com\/blog\/#website\",\"url\":\"https:\/\/careerkarma.com\/blog\/\",\"name\":\"Career Karma\",\"description\":\"Latest Coding Bootcamp News & Career Hacks from Industry Insiders\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/careerkarma.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e\",\"name\":\"Christina Kopecky\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg\",\"contentUrl\":\"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg\",\"caption\":\"Christina Kopecky\"},\"description\":\"Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy, Repl.it, and Educative.\",\"sameAs\":[\"http:\/\/www.linkedin.com\/in\/cmvnk\"],\"url\":\"https:\/\/careerkarma.com\/blog\/author\/christina-kopecky\/\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Dynamic Programming: An Introduction | Career Karma","description":"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.","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:\/\/careerkarma.com\/blog\/dynamic-programming\/","og_locale":"en_US","og_type":"article","og_title":"Dynamic Programming: An Introduction","og_description":"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.","og_url":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/","og_site_name":"Career Karma","article_publisher":"http:\/\/facebook.com\/careerkarmaapp","article_published_time":"2020-09-13T00:20:51+00:00","article_modified_time":"2020-09-13T00:39:16+00:00","og_image":[{"width":1200,"height":675,"url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg","type":"image\/jpeg"}],"author":"Christina Kopecky","twitter_card":"summary_large_image","twitter_creator":"@career_karma","twitter_site":"@career_karma","twitter_misc":{"Written by":"Christina Kopecky","Est. reading time":"10 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#article","isPartOf":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/"},"author":{"name":"Christina Kopecky","@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e"},"headline":"Dynamic Programming: An Introduction","datePublished":"2020-09-13T00:20:51+00:00","dateModified":"2020-09-13T00:39:16+00:00","mainEntityOfPage":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/"},"wordCount":1383,"commentCount":0,"image":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage"},"thumbnailUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg","articleSection":["Software Engineering"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/careerkarma.com\/blog\/dynamic-programming\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/","url":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/","name":"Dynamic Programming: An Introduction | Career Karma","isPartOf":{"@id":"https:\/\/careerkarma.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage"},"image":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage"},"thumbnailUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg","datePublished":"2020-09-13T00:20:51+00:00","dateModified":"2020-09-13T00:39:16+00:00","author":{"@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e"},"description":"Learn about dynamic programming and the differences between naive, top-down, and bottom-up solutions to two popular code challenges.","breadcrumb":{"@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/careerkarma.com\/blog\/dynamic-programming\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#primaryimage","url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg","contentUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2019\/06\/dynamic-programming.jpg","width":1200,"height":675,"caption":"Dynamic Programming (with a Fibonacci spiral)"},{"@type":"BreadcrumbList","@id":"https:\/\/careerkarma.com\/blog\/dynamic-programming\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog","item":"https:\/\/careerkarma.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Software Engineering","item":"https:\/\/careerkarma.com\/blog\/software-engineering-skills\/"},{"@type":"ListItem","position":3,"name":"Dynamic Programming: An Introduction"}]},{"@type":"WebSite","@id":"https:\/\/careerkarma.com\/blog\/#website","url":"https:\/\/careerkarma.com\/blog\/","name":"Career Karma","description":"Latest Coding Bootcamp News & Career Hacks from Industry Insiders","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/careerkarma.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/ae0cdc4a5d198690d78482646894074e","name":"Christina Kopecky","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/careerkarma.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg","contentUrl":"https:\/\/careerkarma.com\/blog\/wp-content\/uploads\/2020\/06\/image-3-150x150.jpg","caption":"Christina Kopecky"},"description":"Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy, Repl.it, and Educative.","sameAs":["http:\/\/www.linkedin.com\/in\/cmvnk"],"url":"https:\/\/careerkarma.com\/blog\/author\/christina-kopecky\/"}]}},"_links":{"self":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts\/3350","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/comments?post=3350"}],"version-history":[{"count":0,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/posts\/3350\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/media\/22552"}],"wp:attachment":[{"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/media?parent=3350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/categories?post=3350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/careerkarma.com\/blog\/wp-json\/wp\/v2\/tags?post=3350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}