{"id":10106,"date":"2025-09-26T14:27:02","date_gmt":"2025-09-26T08:57:02","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10106"},"modified":"2025-09-26T14:48:20","modified_gmt":"2025-09-26T09:18:20","slug":"introduction-to-dynamic-programming","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/introduction-to-dynamic-programming\/","title":{"rendered":"Introduction to Dynamic Programming"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\">\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>Dynamic Programming<\/h2>\n    <p><strong>Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s.<\/strong><\/p>\n    <ul>\n        <li>It is an optimisation technique use along with data structures.<\/li>\n        <li>Applied in mathematics and optimisation.<\/li>\n    <\/ul>\n\n    <h2>Dynamic Programming = Intelligent Laziness<\/h2>\n    <p><strong><code>Dynamic Programming (DP) can be thought of as intelligent laziness. The idea is simple:<\/code><\/strong><\/p>\n   <ul>\n    <li>We want to solve a <strong>problem efficiently<\/strong>, without doing the same <strong>hard work again and again<\/strong>.<\/li>\n    <li>In a <strong>brute-force approach<\/strong>, we try to solve a problem by <code>breaking it down into smaller subproblems<\/code>. However, many of these <code>subproblems turn out to be repeated<\/code>. If we solve them every single time they appear, we end up wasting a lot of time and effort.<\/li>\n    <li><code>Dynamic Programming<\/code> <strong>avoids this waste<\/strong>. Instead of <strong>re-solving<\/strong> the same <code>subproblem multiple times<\/code>, we solve it once, store the result (in memory, an array, or a table), and reuse it whenever the <code>same subproblem<\/code> appears again.<\/li>\n<\/ul>\n\n    <h2>This way:<\/h2>\n    <ul>\n        <li>We still break down a <code>big problem into smaller ones<\/code> <strong>(divide and conquer)<\/strong>.<\/li>\n        <li>But we <strong>don\u2019t repeat ourselves<\/strong> \u2014 we remember what we have already done.<\/li>\n        <li>This makes the <code>solution<\/code> much <code>faster<\/code> than the naive <strong>brute-force approach<\/strong>.<\/li>\n    <\/ul>\n\n    <h2>In-short DP means: <\/h2>\n    <ul>\n    \n        <li><code>Break the big problem into subproblems<\/code>.<\/li>\n        <li><code>Solve each subproblem only once<\/code>.<\/li>\n        <li><code>Store the result<\/code>.<\/li>\n        <li><code>Reuse it when needed<\/code>.<\/li>\n        <\/code>\n    <\/ul>\n\n    <h2>Example of DP:<\/h2>\n    <ul>\n        <li>1. Google Maps<\/li>\n        <li>2. DNA Matching<\/li>\n        <li>3. Alignment Algorithms <\/li>\n        <li>4. Stock market Predictions<\/li>\n        <li>5. Video Games AI<\/li>\n    <\/ul>\n\n    <h2>\n        Dynamic Programming:\n    <\/h2>\n    <p>DP is an <strong>optimisation technique<\/strong> used to solve problems that can be broken down into <code>overlapping subproblems<\/code> that have an <strong>optimal structure<\/strong>. <\/p>\n    <ul>\n        <li><strong>Overlapping Subproblems:<\/strong> While solving a big problems, we repeatedly solve same smaller problems. <\/li>\n        <li><strong>Optimal Substructure:<\/strong> The solution to the big problem can be constructed from solution of smaller sub problems.<\/li>\n    <\/ul>\n\n    <h3>Remember:<\/h3>\n    <ul>\n        <li><strong><i>\u201cDP is about storing and reusing the results of smaller sub problems, instead of recalculating again&#8221;.<\/i><\/strong><\/li>\n        <li><i><strong>Dynamic Programming is simply optimized recursion<\/strong> To understand DP, you must first <code>understand recursion<\/code>.<\/i><\/li>\n    <\/ul>\n    <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/09\/Screenshot-2025-09-25-at-3.13.09\u202fPM.png\" alt=\"\">\n\n    <!-- <h2>Dry Run<\/h2> \n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\"> \n  <p><strong>Input:<\/strong> <code>arr = [1, 0, 2]<\/code><\/p> \n  \n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\n\nStep 0: Start Function: candy(arr)\narr = [1, 0, 2]\nn = arr.length = 3\nInitialize ltr = Array(n).fill(1) \u2192 [1, 1, 1]\n\nStep 1: Left-to-right pass (populate ltr)\nIteration (i = 1): arr[1] = 0, arr[0] = 1\n- Condition: 0 > 1 \u2192 false\n- ltr stays [1, 1, 1]\n\nIteration (i = 2): arr[2] = 2, arr[1] = 0\n- Condition: 2 > 0 \u2192 true\n- ltr[2] = ltr[1] + 1 = 1 + 1 = 2\n- ltr becomes [1, 1, 2]\n\nStep 2: Right-to-left pass (populate rtl)\nInitialize rtl = Array(n).fill(1) \u2192 [1, 1, 1]\n\nIteration (i = 1): arr[1] = 0, arr[2] = 2\n- Condition: 0 > 2 \u2192 false\n- rtl stays [1, 1, 1]\n\nIteration (i = 0): arr[0] = 1, arr[1] = 0\n- Condition: 1 > 0 \u2192 true\n- rtl[0] = rtl[1] + 1 = 1 + 1 = 2\n- rtl becomes [2, 1, 1]\n\nStep 3: Sum up using max(ltr[i], rtl[i])\nans = 0\n\ni = 0: max(2, 1) = 2 \u2192 ans = 2  \ni = 1: max(1, 1) = 1 \u2192 ans = 3  \ni = 2: max(1, 2) = 2 \u2192 ans = 5  \n\nStep 4: End\nReturn ans = 5\n  <\/pre> \n  \n  <p><strong>Output:<\/strong> <code>5<\/code><\/p> \n<\/div> -->\n\n<\/div>\n\n\n    <!-- <div class=\"wp_blog_code-tabs-header\">\n      <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div> -->\n\n    <!-- <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\nvar candy = function(arr) {\n    let n = arr.length;\n    let ltr = Array(n).fill(1);\n\n    for(let i=1; i<n; i++){\n        if(arr[i] > arr[i-1]){\n            ltr[i] = ltr[i-1] + 1;\n        }\n    }\n\n    let rtl = Array(n).fill(1);\n    for(let i=n-2; i>=0; i--){\n        if(arr[i] > arr[i+1]) {\n            rtl[i] = rtl[i+1] + 1;\n        }\n    }\n    let ans = 0; \n    for(let i=0; i < n; i++){\n        ans = ans + Math.max(rtl[i], ltr[i]);\n    }\n    return ans;\n};\n<\/code><\/pre>\n    <\/div> -->\n    <!-- <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\ndef candy(arr):\n    n = len(arr)\n    if n == 0:\n        return 0\n    ltr = [1] * n\n    rtl = [1] * n\n    for i in range(1, n):\n        if arr[i] > arr[i-1]:\n            ltr[i] = ltr[i-1] + 1\n    for i in range(n-2, -1, -1):\n        if arr[i] > arr[i+1]:\n            rtl[i] = rtl[i+1] + 1\n    ans = 0\n    for i in range(n):\n        ans += max(ltr[i], rtl[i])\n    return ans\nif __name__ == \"__main__\":\n    print(candy([1, 0, 2]))\n      <\/code><\/pre>\n    <\/div> -->\n    <!-- <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\npublic class CandyProblem {\n    public static int candy(int[] arr) {\n        int n = arr.length;\n        if (n == 0) return 0;\n\n        int[] ltr = new int[n];\n        int[] rtl = new int[n];\n        for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }\n\n        for (int i = 1; i < n; i++) {\n            if (arr[i] > arr[i - 1]) ltr[i] = ltr[i - 1] + 1;\n        }\n\n        for (int i = n - 2; i >= 0; i--) {\n            if (arr[i] > arr[i + 1]) rtl[i] = rtl[i + 1] + 1;\n        }\n\n        int ans = 0;\n        for (int i = 0; i < n; i++) ans += Math.max(ltr[i], rtl[i]);\n        return ans;\n    }\n    public static void main(String[] args) {\n        int[] ratings = {1, 0, 2};\n        System.out.println(candy(ratings)); \n    }\n}\n    <\/code><\/pre>\n    <\/div> -->\n\n    <!-- <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n\nusing namespace std;\nint candy(const vector<int>& arr) {\n    int n = arr.size();\n    if (n == 0) return 0;\n    vector<int> ltr(n, 1), rtl(n, 1);\n    for (int i = 1; i < n; ++i) {\n        if (arr[i] > arr[i-1]) ltr[i] = ltr[i-1] + 1;\n    }\n    for (int i = n - 2; i >= 0; --i) {\n        if (arr[i] > arr[i+1]) rtl[i] = rtl[i+1] + 1;\n    }\n    int ans = 0;\n    for (int i = 0; i < n; ++i) ans += max(ltr[i], rtl[i]);\n    return ans;\n}\nint main() {\n    vector<int> ratings = {1, 0, 2};\n    cout << candy(ratings) << '\\n';\n    return 0;\n}\n<\/code><\/pre>\n    <\/div> \n\n    <!-- <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nint candy(int *arr, int n) {\n    if (n == 0) return 0;\n    int *ltr = (int*)malloc(sizeof(int) * n);\n    int *rtl = (int*)malloc(sizeof(int) * n);\n    for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }\n\n    for (int i = 1; i < n; i++) {\n        if (arr[i] > arr[i-1]) ltr[i] = ltr[i-1] + 1;\n    }\n    for (int i = n - 2; i >= 0; i--) {\n        if (arr[i] > arr[i+1]) rtl[i] = rtl[i+1] + 1;\n    }\n    int ans = 0;\n    for (int i = 0; i < n; i++) ans += (ltr[i] > rtl[i] ? ltr[i] : rtl[i]);\n\n    free(ltr);\n    free(rtl);\n    return ans;\n}\nint main() {\n    int ratings[] = {1, 0, 2};\n    int n = sizeof(ratings) \/ sizeof(ratings[0]);\n    printf(\"%d\\n\", candy(ratings, n)); \n    return 0;\n}\n <\/code><\/pre>\n    <\/div> -->\n\n    <!-- <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n      <pre><code class=\"language-csharp\">\nusing System;\nclass Program {\n    static int Candy(int[] arr) {\n        int n = arr.Length;\n        if (n == 0) return 0;\n        int[] ltr = new int[n];\n        int[] rtl = new int[n];\n        for (int i = 0; i < n; i++) { ltr[i] = 1; rtl[i] = 1; }\n        for (int i = 1; i < n; i++) {\n            if (arr[i] > arr[i - 1]) ltr[i] = ltr[i - 1] + 1;\n        }\n        for (int i = n - 2; i >= 0; i--) {\n            if (arr[i] > arr[i + 1]) rtl[i] = rtl[i + 1] + 1;\n        }\n        int ans = 0;\n        for (int i = 0; i < n; i++) ans += Math.Max(ltr[i], rtl[i]);\n        return ans;\n    }\n    static void Main() {\n        int[] ratings = {1, 0, 2};\n        Console.WriteLine(Candy(ratings)); \n    }\n}\n      <\/code><\/pre>\n    <\/div> -->\n\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Dynamic Programming Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s. It is an optimisation technique use along with data structures. Applied in mathematics and optimisation. Dynamic Programming = Intelligent Laziness Dynamic Programming (DP) can be thought of as intelligent laziness.<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,176,175,211,811,810,174,172,173],"tags":[],"class_list":{"0":"post-10106","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms","7":"category-csharp","8":"category-cplusplus","9":"category-data-structures","10":"category-data-structures-and-algorithms","11":"category-dsa","12":"category-java","13":"category-javascript","14":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10106","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10106"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10106\/revisions"}],"predecessor-version":[{"id":10124,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10106\/revisions\/10124"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10106"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10106"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10106"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}