{"id":878,"date":"2025-07-23T15:31:02","date_gmt":"2025-07-23T15:31:02","guid":{"rendered":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/"},"modified":"2025-07-23T15:31:02","modified_gmt":"2025-07-23T15:31:02","slug":"dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence","status":"publish","type":"post","link":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/","title":{"rendered":"Dynamic Programming (DP) &#8211; Part 2: Common DP Patterns (Knapsack, Longest Subsequence)"},"content":{"rendered":"<h1>Dynamic Programming (DP) &#8211; Part 2: Common Dynamic Programming Patterns (Knapsack, Longest Subsequence)<\/h1>\n<p>Welcome back to our deep dive into Dynamic Programming (DP)! In this second installment, we&#8217;re rolling up our sleeves and tackling two fundamental and frequently encountered <strong>Common Dynamic Programming Patterns<\/strong>: the Knapsack problem and the Longest Common Subsequence (LCS) problem. These patterns are not only essential for mastering DP but also serve as building blocks for solving a wide array of optimization challenges. Get ready to expand your algorithmic toolkit and boost your problem-solving prowess! \ud83d\ude80<\/p>\n<h2>Executive Summary<\/h2>\n<p>This blog post provides a comprehensive overview of two core Dynamic Programming (DP) patterns: the Knapsack problem and the Longest Common Subsequence (LCS). We&#8217;ll explore both the 0\/1 Knapsack variation, where each item can either be entirely included or excluded, and the unbounded Knapsack, where multiple instances of the same item can be included. For LCS, we&#8217;ll demonstrate how to find the longest subsequence common to two or more strings. The goal is to equip you with practical knowledge and coding examples to confidently approach and solve these problems, and more generally, any DP problems you may encounter. We&#8217;ll use intuitive explanations and code examples to solidify your understanding. By mastering these fundamental patterns, you&#8217;ll be well-equipped to tackle more complex DP challenges and ace those coding interviews! \ud83c\udfaf<\/p>\n<h2>0\/1 Knapsack Problem \ud83c\udf92<\/h2>\n<p>The 0\/1 Knapsack problem is a classic optimization problem where you have a knapsack with a limited weight capacity and a set of items, each with a weight and a value. The goal is to maximize the total value of items you can fit into the knapsack without exceeding its weight capacity. Each item can either be taken (1) or not taken (0), hence the name 0\/1 Knapsack.<\/p>\n<ul>\n<li>\ud83d\udca1 This is a core DP problem useful in resource allocation scenarios.<\/li>\n<li>\ud83d\udcc8 The DP approach involves building a table to store optimal values for different subproblems.<\/li>\n<li>\u2705 0\/1 indicates we can take an item or leave it; no fractions allowed.<\/li>\n<li>\u2728 Optimal substructure: the optimal solution includes optimal solutions to subproblems.<\/li>\n<li>\ud83e\udd16 Overlapping subproblems: Subproblems are solved repeatedly, making DP efficient.<\/li>\n<\/ul>\n<h3>Example: 0\/1 Knapsack<\/h3>\n<p>Let&#8217;s say you have a knapsack with a capacity of 5, and the following items:<\/p>\n<table>\n<thead>\n<tr>\n<th>Item<\/th>\n<th>Weight<\/th>\n<th>Value<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>A<\/td>\n<td>2<\/td>\n<td>6<\/td>\n<\/tr>\n<tr>\n<td>B<\/td>\n<td>2<\/td>\n<td>10<\/td>\n<\/tr>\n<tr>\n<td>C<\/td>\n<td>3<\/td>\n<td>12<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>The goal is to determine which items to include to maximize the total value without exceeding the capacity of 5.<\/p>\n<h3>Python Code: 0\/1 Knapsack<\/h3>\n<pre><code class=\"language-python\">\ndef knapsack_01(capacity, weights, values, n):\n    \"\"\"\n    Solves the 0\/1 Knapsack problem using dynamic programming.\n\n    Args:\n        capacity: The maximum weight capacity of the knapsack.\n        weights: A list of the weights of the items.\n        values: A list of the values of the items.\n        n: The number of items.\n\n    Returns:\n        The maximum total value that can be carried in the knapsack.\n    \"\"\"\n\n    # Initialize a table to store the maximum values for different capacities and items\n    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]\n\n    # Build the table in a bottom-up manner\n    for i in range(1, n + 1):\n        for w in range(1, capacity + 1):\n            if weights[i-1] &lt;= w:\n                # If the current item&#039;s weight is less than or equal to the current capacity,\n                # choose the maximum between including the item and excluding it\n                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])\n            else:\n                # If the current item&#039;s weight is greater than the current capacity,\n                # exclude the item\n                dp[i][w] = dp[i-1][w]\n\n    # The maximum value is stored in the bottom-right cell of the table\n    return dp[n][capacity]\n\n# Example usage:\nvalues = [6, 10, 12]\nweights = [2, 2, 3]\ncapacity = 5\nn = len(values)\n\nmax_value = knapsack_01(capacity, weights, values, n)\nprint(&quot;Maximum value:&quot;, max_value)  # Output: Maximum value: 22\n\n    <\/code><\/pre>\n<p><strong>Explanation:<\/strong> The code uses a 2D array <code>dp<\/code> to store the maximum value achievable for each capacity and item.  We iterate through the items, and for each item, we decide whether to include it or not based on whether it maximizes the value while staying within the capacity. The final result, 22, represents the maximum value that can be obtained by optimally choosing items A and C. \ud83d\udc4d<\/p>\n<h2>Unbounded Knapsack Problem \u267e\ufe0f<\/h2>\n<p>The Unbounded Knapsack problem is similar to the 0\/1 Knapsack, but with one key difference: you can take multiple instances of the same item. In other words, you are not limited to taking an item just once. This adds another layer of complexity, but DP can handle it efficiently.<\/p>\n<ul>\n<li>\ud83d\udca1 Useful in scenarios where you can take multiple units of the same item.<\/li>\n<li>\ud83d\udcc8 The DP approach builds on the 0\/1 Knapsack, allowing for multiple selections.<\/li>\n<li>\u2705 &#8220;Unbounded&#8221; means you can take as many of each item as you want.<\/li>\n<li>\u2728 Optimal substructure still applies: Optimal solutions build upon subproblems.<\/li>\n<li>\ud83e\udd16 Overlapping subproblems are also present, leading to efficient DP solutions.<\/li>\n<\/ul>\n<h3>Example: Unbounded Knapsack<\/h3>\n<p>Consider a knapsack with a capacity of 10, and the following items:<\/p>\n<table>\n<thead>\n<tr>\n<th>Item<\/th>\n<th>Weight<\/th>\n<th>Value<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>A<\/td>\n<td>3<\/td>\n<td>5<\/td>\n<\/tr>\n<tr>\n<td>B<\/td>\n<td>4<\/td>\n<td>7<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>The goal is to maximize the total value by selecting any number of items A and B, as long as the total weight does not exceed 10.<\/p>\n<h3>Python Code: Unbounded Knapsack<\/h3>\n<pre><code class=\"language-python\">\ndef unbounded_knapsack(capacity, weights, values, n):\n    \"\"\"\n    Solves the Unbounded Knapsack problem using dynamic programming.\n\n    Args:\n        capacity: The maximum weight capacity of the knapsack.\n        weights: A list of the weights of the items.\n        values: A list of the values of the items.\n        n: The number of items.\n\n    Returns:\n        The maximum total value that can be carried in the knapsack.\n    \"\"\"\n\n    # Initialize a table to store the maximum values for different capacities\n    dp = [0 for _ in range(capacity + 1)]\n\n    # Iterate through all possible capacities\n    for w in range(1, capacity + 1):\n        # Iterate through all items\n        for i in range(n):\n            if weights[i] &lt;= w:\n                # If the current item&#039;s weight is less than or equal to the current capacity,\n                # update the maximum value by including the item (potentially multiple times)\n                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])\n\n    # The maximum value is stored in the last cell of the table\n    return dp[capacity]\n\n# Example usage:\nvalues = [5, 7]\nweights = [3, 4]\ncapacity = 10\nn = len(values)\n\nmax_value = unbounded_knapsack(capacity, weights, values, n)\nprint(&quot;Maximum value:&quot;, max_value)  # Output: Maximum value: 17\n    <\/code><\/pre>\n<p><strong>Explanation:<\/strong> Here, the <code>dp<\/code> array is 1D. We iterate through each capacity and each item.  If the item&#8217;s weight is less than the current capacity, we check if adding that item (and potentially more of the same) increases the total value compared to what we already have for that capacity. This approach allows us to optimally select multiple instances of each item. The final result, 17, is obtained by taking two items of type B (2 * 7 = 14) and optimizing with item A once (5). \ud83d\ude09<\/p>\n<h2>Longest Common Subsequence (LCS) \ud83d\udcdd<\/h2>\n<p>The Longest Common Subsequence (LCS) problem is another classic DP challenge. Given two sequences, the goal is to find the length of the longest subsequence that is common to both. A subsequence doesn&#8217;t have to be contiguous, but the elements must maintain their original order.<\/p>\n<ul>\n<li>\ud83d\udca1 This is essential for sequence comparison tasks like DNA sequencing.<\/li>\n<li>\ud83d\udcc8 DP builds a table to track subsequence lengths for different prefixes.<\/li>\n<li>\u2705 Subsequence elements don&#8217;t need to be consecutive, but order matters.<\/li>\n<li>\u2728 Optimal substructure is key: LCS of prefixes leads to the overall LCS.<\/li>\n<li>\ud83e\udd16 Overlapping subproblems: Repeatedly computing LCS of sub-strings.<\/li>\n<\/ul>\n<h3>Example: LCS<\/h3>\n<p>Consider two strings:<\/p>\n<ul>\n<li>String 1: &#8220;ABCBDAB&#8221;<\/li>\n<li>String 2: &#8220;BDCABA&#8221;<\/li>\n<\/ul>\n<p>The longest common subsequence is &#8220;BCBA&#8221;, which has a length of 4.<\/p>\n<h3>Python Code: LCS<\/h3>\n<pre><code class=\"language-python\">\ndef longest_common_subsequence(s1, s2):\n    \"\"\"\n    Finds the length of the Longest Common Subsequence (LCS) of two strings using dynamic programming.\n\n    Args:\n        s1: The first string.\n        s2: The second string.\n\n    Returns:\n        The length of the LCS.\n    \"\"\"\n\n    # Initialize a table to store lengths of LCS for different prefixes\n    n = len(s1)\n    m = len(s2)\n    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n\n    # Build the table in a bottom-up manner\n    for i in range(1, n + 1):\n        for j in range(1, m + 1):\n            if s1[i-1] == s2[j-1]:\n                # If the characters match, increment the LCS length by 1\n                dp[i][j] = dp[i-1][j-1] + 1\n            else:\n                # If the characters don't match, take the maximum LCS length from the previous row or column\n                dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n\n    # The length of the LCS is stored in the bottom-right cell of the table\n    return dp[n][m]\n\n# Example usage:\ns1 = \"ABCBDAB\"\ns2 = \"BDCABA\"\n\nlcs_length = longest_common_subsequence(s1, s2)\nprint(\"Length of LCS:\", lcs_length)  # Output: Length of LCS: 4\n    <\/code><\/pre>\n<p><strong>Explanation:<\/strong> The <code>dp<\/code> table stores the lengths of the LCS for different prefixes of <code>s1<\/code> and <code>s2<\/code>. When the characters at <code>s1[i-1]<\/code> and <code>s2[j-1]<\/code> match, we increment the LCS length. Otherwise, we take the maximum LCS length from either excluding a character from <code>s1<\/code> or excluding a character from <code>s2<\/code>. The final value in <code>dp[n][m]<\/code> is the length of the LCS for the entire strings. \ud83c\udf89<\/p>\n<h2>Real-World Applications of DP Problems \ud83c\udfe2<\/h2>\n<p>Dynamic programming algorithms aren&#8217;t confined to theoretical exercises. They have profound implications across diverse real-world applications, impacting industries ranging from finance to logistics.<\/p>\n<ul>\n<li><b>Finance:<\/b> Portfolio Optimization: DP is used to select the optimal set of investments to maximize returns while minimizing risk, akin to the Knapsack problem. <\/li>\n<li><b>Bioinformatics:<\/b> Sequence Alignment: In genetics and bioinformatics, the Longest Common Subsequence (LCS) and similar DP techniques are essential for aligning DNA or protein sequences to identify similarities and evolutionary relationships.<\/li>\n<li><b>Logistics:<\/b> Supply Chain Management:Optimizing the supply chain involves minimizing costs while meeting demand. DP is applied in inventory management, route planning, and resource allocation to make informed decisions. <a href=\"https:\/\/dohost.us\">DoHost<\/a> services ensure efficient and scalable hosting for applications that manage complex supply chain data, providing reliable infrastructure for critical operations.<\/li>\n<li><b>Artificial Intelligence:<\/b> Reinforcement Learning: DP is used in reinforcement learning for policy optimization, where the algorithm learns to make decisions in a dynamic environment to maximize a reward. <\/li>\n<\/ul>\n<h2>FAQ \u2753<\/h2>\n<h2>How do I identify a problem that can be solved with Dynamic Programming?<\/h2>\n<p>Dynamic Programming problems typically exhibit two key properties: optimal substructure and overlapping subproblems. Optimal substructure means that the optimal solution to the problem can be constructed from optimal solutions to its subproblems. Overlapping subproblems mean that the same subproblems are solved repeatedly. Identifying these properties is crucial for determining if DP is the right approach. <\/p>\n<h2>What is the difference between Memoization and Tabulation in Dynamic Programming?<\/h2>\n<p>Memoization (top-down) starts with the original problem and breaks it down into subproblems, solving each subproblem only once and storing the results in a cache (e.g., dictionary or array) to avoid recomputation. Tabulation (bottom-up) starts with the smallest subproblems and iteratively builds up the solution to the larger problem, storing the results in a table (usually an array). Tabulation generally avoids recursion overhead and can be more efficient.<\/p>\n<h2>How do I optimize space complexity in Dynamic Programming solutions?<\/h2>\n<p>Space complexity can often be optimized by carefully analyzing the dependencies between subproblems. For example, in many DP problems, you only need to keep track of the previous row or column of the DP table. By reusing space and overwriting values that are no longer needed, you can reduce the space complexity from O(n^2) to O(n). Additionally, identify if all rows\/columns of the table is needed, or only certain sub problems need to be cached. <\/p>\n<h2>Conclusion<\/h2>\n<p>Mastering <strong>Common Dynamic Programming Patterns<\/strong> like the Knapsack problem and the Longest Common Subsequence is crucial for any aspiring algorithm enthusiast. These patterns provide a solid foundation for tackling a wide range of optimization problems. By understanding the underlying principles of optimal substructure and overlapping subproblems, and by practicing with various examples, you&#8217;ll be well-equipped to solve complex problems efficiently. Remember, practice makes perfect! Keep honing your DP skills, and you&#8217;ll be amazed at the problems you can solve. Good luck and happy coding! \ud83d\ude80<\/p>\n<h3>Tags<\/h3>\n<p>    Dynamic Programming, Knapsack, LCS, Algorithms, Optimization<\/p>\n<h3>Meta Description<\/h3>\n<p>    Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dynamic Programming (DP) &#8211; Part 2: Common Dynamic Programming Patterns (Knapsack, Longest Subsequence) Welcome back to our deep dive into Dynamic Programming (DP)! In this second installment, we&#8217;re rolling up our sleeves and tackling two fundamental and frequently encountered Common Dynamic Programming Patterns: the Knapsack problem and the Longest Common Subsequence (LCS) problem. These patterns [&hellip;]<\/p>\n","protected":false},"author":0,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3395],"tags":[627,2888,307,3521,935,2975,3525,3524,2083,915,2247,2967],"class_list":["post-878","post","type-post","status-publish","format-standard","hentry","category-data-structures-and-algorithms","tag-algorithms","tag-coding-interview","tag-data-structures","tag-dp","tag-dynamic-programming","tag-knapsack-problem","tag-lcs","tag-longest-common-subsequence","tag-memoization","tag-optimization","tag-problem-solving","tag-tabulation"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v25.0 (Yoast SEO v25.0) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence) - Developers Heaven<\/title>\n<meta name=\"description\" content=\"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence)\" \/>\n<meta property=\"og:description\" content=\"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/\" \/>\n<meta property=\"og:site_name\" content=\"Developers Heaven\" \/>\n<meta property=\"article:published_time\" content=\"2025-07-23T15:31:02+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/via.placeholder.com\/600x400?text=Dynamic+Programming+DP+-+Part+2+Common+DP+Patterns+Knapsack+Longest+Subsequence\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"10 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/\",\"url\":\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/\",\"name\":\"Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence) - Developers Heaven\",\"isPartOf\":{\"@id\":\"https:\/\/developers-heaven.net\/blog\/#website\"},\"datePublished\":\"2025-07-23T15:31:02+00:00\",\"author\":{\"@id\":\"\"},\"description\":\"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.\",\"breadcrumb\":{\"@id\":\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/developers-heaven.net\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Dynamic Programming (DP) &#8211; Part 2: Common DP Patterns (Knapsack, Longest Subsequence)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/developers-heaven.net\/blog\/#website\",\"url\":\"https:\/\/developers-heaven.net\/blog\/\",\"name\":\"Developers Heaven\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/developers-heaven.net\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence) - Developers Heaven","description":"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.","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:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/","og_locale":"en_US","og_type":"article","og_title":"Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence)","og_description":"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.","og_url":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/","og_site_name":"Developers Heaven","article_published_time":"2025-07-23T15:31:02+00:00","og_image":[{"url":"https:\/\/via.placeholder.com\/600x400?text=Dynamic+Programming+DP+-+Part+2+Common+DP+Patterns+Knapsack+Longest+Subsequence","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"10 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/","url":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/","name":"Dynamic Programming (DP) - Part 2: Common DP Patterns (Knapsack, Longest Subsequence) - Developers Heaven","isPartOf":{"@id":"https:\/\/developers-heaven.net\/blog\/#website"},"datePublished":"2025-07-23T15:31:02+00:00","author":{"@id":""},"description":"Dive into common Dynamic Programming patterns like Knapsack and Longest Subsequence. Master optimization techniques and solve complex problems efficiently.","breadcrumb":{"@id":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/developers-heaven.net\/blog\/dynamic-programming-dp-part-2-common-dp-patterns-knapsack-longest-subsequence\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/developers-heaven.net\/blog\/"},{"@type":"ListItem","position":2,"name":"Dynamic Programming (DP) &#8211; Part 2: Common DP Patterns (Knapsack, Longest Subsequence)"}]},{"@type":"WebSite","@id":"https:\/\/developers-heaven.net\/blog\/#website","url":"https:\/\/developers-heaven.net\/blog\/","name":"Developers Heaven","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/developers-heaven.net\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"_links":{"self":[{"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/posts\/878","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"replies":[{"embeddable":true,"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/comments?post=878"}],"version-history":[{"count":0,"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/posts\/878\/revisions"}],"wp:attachment":[{"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/media?parent=878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/categories?post=878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/developers-heaven.net\/blog\/wp-json\/wp\/v2\/tags?post=878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}