Day 10: Dynamic Programming & Greedy Algorithms

What You'll Learn Today

• Fundamentals of Dynamic Programming (DP)
• Top-down (memoization) vs. bottom-up (tabulation)
• The greedy approach
• When to use DP vs. greedy

---

Dynamic Programming (DP)

Dynamic Programming breaks a problem into overlapping subproblems, solves each one only once, and stores the results for reuse.

flowchart TB
    subgraph NaiveRecursion["Naive Recursion (Redundant Work)"]
        F5["fib(5)"] --> F4["fib(4)"]
        F5 --> F3a["fib(3)"]
        F4 --> F3b["fib(3)"]
        F4 --> F2a["fib(2)"]
        F3a --> F2b["fib(2)"]
        F3a --> F1a["fib(1)"]
        F3b --> F2c["fib(2)"]
        F3b --> F1b["fib(1)"]
    end
    style F3a fill:#ef4444,color:#fff
    style F3b fill:#ef4444,color:#fff
    style F2a fill:#f59e0b,color:#fff
    style F2b fill:#f59e0b,color:#fff
    style F2c fill:#f59e0b,color:#fff

When DP Applies

1. Overlapping subproblems: The same computation occurs multiple times
2. Optimal substructure: Optimal solutions to subproblems combine to form the overall optimal solution

---

Top-Down (Memoization)

Implemented with recursion + caching.

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(50)); // 12586269025

---

Bottom-Up (Tabulation)

Solve smaller subproblems first and build up.

function fibTable(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// Space-optimized: O(1) space
function fibOptimized(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

Top-Down vs. Bottom-Up

Feature	Top-Down	Bottom-Up
Implementation	Recursion + memo	Loop + table
Subproblems	Computes only needed ones	Computes all
Stack usage	Uses recursion stack	None
Intuition	Natural recursive thinking	Requires table design

---

Classic DP Problems

1. Climbing Stairs

Count ways to climb n stairs taking 1 or 2 steps at a time.

function climbStairs(n) {
  if (n <= 2) return n;
  const dp = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(climbStairs(5)); // 8

2. Coin Change

Find the minimum number of coins to make a target amount.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] + 1 < dp[i]) {
        dp[i] = dp[i - coin] + 1;
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 10, 25], 36)); // 3 (25 + 10 + 1)
console.log(coinChange([2], 3));              // -1

flowchart LR
    subgraph DP["dp array (coins=[1,5,10], amount=11)"]
        D0["dp[0]\n0"]
        D1["dp[1]\n1"]
        D5["dp[5]\n1"]
        D10["dp[10]\n1"]
        D11["dp[11]\n2"]
    end
    D0 -->|"+1"| D1
    D0 -->|"+5"| D5
    D0 -->|"+10"| D10
    D10 -->|"+1"| D11
    style D0 fill:#22c55e,color:#fff
    style D11 fill:#3b82f6,color:#fff

3. Longest Common Subsequence (LCS)

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // 3

4. 0/1 Knapsack

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  return dp[n][capacity];
}

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack(weights, values, 8)); // 10

5. Longest Increasing Subsequence (LIS)

function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4

---

Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, aiming for a globally optimal result.

flowchart TB
    subgraph Greedy["Greedy Approach"]
        S["Problem"] --> C1["Choice 1\n(pick best)"]
        C1 --> C2["Choice 2\n(pick best)"]
        C2 --> C3["Choice 3\n(pick best)"]
        C3 --> R["Solution"]
    end
    style Greedy fill:#22c55e,color:#fff

When Greedy Works

1. Greedy choice property: A locally optimal choice leads to a globally optimal solution
2. Optimal substructure: Optimal solutions to subproblems contribute to the overall optimum

---

Greedy Examples

1. Coin Change (Greedy)

function minCoinsGreedy(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  const used = [];

  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
      used.push(coin);
    }
  }

  return amount === 0 ? { count, used } : null;
}

console.log(minCoinsGreedy([1, 5, 10, 25], 36));
// { count: 3, used: [25, 10, 1] }

Note: Greedy doesn't guarantee optimal results for all coin sets. For [1, 3, 4] with amount 6, greedy gives 4+1+1=3 coins, but the optimal answer is 3+3=2 coins.

2. Activity Selection

Select the maximum number of non-overlapping activities.

function activitySelection(activities) {
  activities.sort((a, b) => a.end - b.end);

  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selected;
}

const activities = [
  { name: "A", start: 1, end: 4 },
  { name: "B", start: 3, end: 5 },
  { name: "C", start: 0, end: 6 },
  { name: "D", start: 5, end: 7 },
  { name: "E", start: 3, end: 9 },
  { name: "F", start: 5, end: 9 },
  { name: "G", start: 6, end: 10 },
  { name: "H", start: 8, end: 11 },
];

console.log(activitySelection(activities));
// [A, D, H] — 3 activities

3. Fractional Knapsack

function fractionalKnapsack(items, capacity) {
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

  let totalValue = 0;
  let remaining = capacity;

  for (const item of items) {
    if (remaining <= 0) break;
    const take = Math.min(item.weight, remaining);
    totalValue += (take / item.weight) * item.value;
    remaining -= take;
  }

  return totalValue;
}

const items = [
  { weight: 10, value: 60 },
  { weight: 20, value: 100 },
  { weight: 30, value: 120 },
];

console.log(fractionalKnapsack(items, 50)); // 240

---

DP vs. Greedy

Feature	Dynamic Programming	Greedy
Approach	Solves all subproblems	Picks local optimum
Optimality	Always guaranteed	Not always guaranteed
Complexity	Usually higher	Usually lower
Implementation	Table/memoization	Simple loop
Examples	0/1 Knapsack, LCS	Activity selection, coin change

flowchart TB
    Q1{"Optimal substructure?"}
    Q1 -->|No| BF["Brute Force"]
    Q1 -->|Yes| Q2{"Greedy choice\nproperty?"}
    Q2 -->|Yes| G["Greedy"]
    Q2 -->|No| Q3{"Overlapping\nsubproblems?"}
    Q3 -->|Yes| DP["Dynamic Programming"]
    Q3 -->|No| DC["Divide & Conquer"]
    style G fill:#22c55e,color:#fff
    style DP fill:#3b82f6,color:#fff
    style DC fill:#8b5cf6,color:#fff
    style BF fill:#ef4444,color:#fff

---

DP Solution Template

// 1. Define state: dp[i] = ...
// 2. Define transition: dp[i] = f(dp[i-1], ...)
// 3. Define base case: dp[0] = ...
// 4. Define answer: dp[n] or max(dp)

function dpTemplate(input) {
  const n = input.length;

  // Step 1 & 3: Initialize dp with base cases
  const dp = new Array(n).fill(0);
  dp[0] = /* base case */;

  // Step 2: Fill dp table
  for (let i = 1; i < n; i++) {
    dp[i] = /* transition using dp[0..i-1] */;
  }

  // Step 4: Return answer
  return dp[n - 1];
}

---

Summary

Concept	Description
Dynamic Programming	Stores and reuses subproblem results
Memoization	Top-down DP with recursion + cache
Tabulation	Bottom-up DP filling a table from small to large
Greedy	Picks the locally optimal choice at each step
Optimal Substructure	Subproblem optima compose the overall optimum

Key Takeaways

1. DP requires both overlapping subproblems and optimal substructure
2. Bottom-up avoids recursion stack and enables space optimization
3. Greedy is more efficient than DP but applies to fewer problems
4. Identifying the right technique for a problem is critical

---

Practice Problems

Problem 1: Basic

Implement a function to count the number of ways to make a target amount using given coin denominations (use DP).

Problem 2: Intermediate

Find the number of unique paths in an m×n grid from top-left to bottom-right (can only move right or down).

Challenge

Implement a function to find the minimum edit distance (Levenshtein distance) between two strings. Allowed operations: insert, delete, replace.

---

References

• Wikipedia - Dynamic programming
• Wikipedia - Greedy algorithm
• LeetCode - Dynamic Programming

---

Congratulations! You've completed the 10-day journey through data structures and algorithms. Use this knowledge as a foundation and continue practicing on platforms like LeetCode and AtCoder.