Study Notes by Niladri & AI

Session-09-DP1D

Properties1
tagsdynamic-programming, dp-1d, memoization, interview-prep, java

20 min read

Practice Session 9: Dynamic Programming — 1D Problems

Overview

Dynamic programming is the single most tested advanced topic in senior engineer interviews, appearing in roughly 30–40% of hard-tagged problems and regularly in system design discussions (optimal cache policies, resource scheduling). The core discipline is not memorizing formulas — it is recognizing the two structural properties that make DP applicable: overlapping subproblems (the naive recursion solves the same sub-case repeatedly) and optimal substructure (the global optimum is composed of local optima). Master the five problems below and you cover the full 1D DP landscape: Fibonacci-style, decision-at-each-step, subsequence, unbounded knapsack, and string segmentation.

DP Problem-Solving Framework

Before writing a single line of code, work through this five-step protocol out loud in the interview:

Step 1 — Define the state: what does dp[i] represent?

This is the hardest and most important step. A wrong state definition produces a correct-looking recurrence that gives wrong answers. Ask yourself: “What is the minimal information I need to describe the answer for a prefix/suffix of size i?”

  • Climbing Stairs: dp[i] = number of distinct ways to reach step i
  • House Robber: dp[i] = maximum money robbed from houses 0..i (inclusive)
  • LIS: dp[i] = length of the longest increasing subsequence ending at index i
  • Coin Change: dp[i] = minimum coins needed to make exactly amount i
  • Word Break: dp[i] = can s[0..i-1] be segmented using the dictionary?

Step 2 — Write the recurrence relation

The recurrence is the decision rule: given the state definition, how does dp[i] depend on smaller subproblems?

ProblemRecurrence
Climbing Stairsdp[i] = dp[i-1] + dp[i-2]
House Robberdp[i] = max(nums[i] + dp[i-2], dp[i-1])
LISdp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]
Coin Changedp[i] = 1 + min(dp[i-coin]) for each valid coin
Word Breakdp[i] = true if dp[j] && s[j..i-1] ∈ dict for some j < i

Step 3 — Identify base cases

Base cases are the subproblems small enough to answer directly without the recurrence. Missing a base case is the most common source of bugs.

  • Always ask: “What is the answer for an empty input (size 0)?”
  • Climbing Stairs: dp[0] = 1 (one way to be at step 0: do nothing), dp[1] = 1
  • House Robber: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  • LIS: dp[i] = 1 for all i (single element is always an LIS of length 1)
  • Coin Change: dp[0] = 0 (0 coins needed for amount 0)
  • Word Break: dp[0] = true (empty string is trivially segmentable)

Step 4 — Determine evaluation order

Bottom-up DP fills the table from smaller subproblems to larger ones. For 1D problems this is almost always left-to-right (i = 0 to i = n). The rule: dp[i] must only reference indices that have already been computed.

Step 5 — Optimize space

After confirming correctness with the full dp array, ask whether the recurrence only looks back a fixed number of cells. If dp[i] only uses dp[i-1] and dp[i-2], you can reduce the O(n) array to two rolling variables, achieving O(1) space.

Problem 1: Climbing Stairs

Link: LeetCode 70

Quick Summary: You can climb 1 or 2 steps at a time. Given n steps, count the distinct ways to reach the top.

Industry Context: This exact recurrence (Fibonacci-style “how many paths in a DAG”) appears in network topology planning (counting distinct routing paths between two switches with limited hop choices), pipeline stage reachability analysis in compilers, and probabilistic state machines in A/B testing frameworks where each experiment stage can be skipped or taken.

Approach 1: Naive Recursion

// Time: O(2^n)  Space: O(n) recursion stack
public static int climbStairsNaive(int n) {
    if (n <= 1) return 1;
    return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}
  • Time: O(2^n) — the call tree doubles at every step; climbStairs(n-2) is recomputed independently by both branches at every level
  • Space: O(n) — max recursion depth
  • Tradeoff: Correct but completely impractical. For n=45 it makes ~2^45 ≈ 35 trillion calls

Recurrence: ways(n) = ways(n-1) + ways(n-2)

Why? To arrive at step n, the last step was either a 1-step (from step n-1) or a 2-step (from step n-2). These two cases are mutually exclusive and exhaustive — so we add them.

Approach 2: Memoization (Top-Down DP)

// Time: O(n)  Space: O(n) memo + O(n) stack
public static int climbStairsMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return helper(n, memo);
}
 
private static int helper(int n, int[] memo) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    return memo[n];
}
  • Time: O(n) — each of the n+1 subproblems computed exactly once
  • Space: O(n) — memo array + O(n) call stack
  • Key Insight: Memoization converts the binary call tree (exponential) into a straight chain (linear) by short-circuiting repeated subtrees. The structure of the recursion is unchanged; only repeated work is eliminated.

Approach 3: Bottom-Up DP (Tabulation)

// Time: O(n)  Space: O(n) dp array
public static int climbStairsDP(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1;  dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
  • Time: O(n)
  • Space: O(n)
  • Tradeoff: No recursion overhead. Fills the table left-to-right. dp[i] is read from already-computed cells, so no stack needed.

Approach 4: Space-Optimized (O(1) Rolling Variables)

// Time: O(n)  Space: O(1)
public static int climbStairsOptimal(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
  • Time: O(n)
  • Space: O(1) — only two variables regardless of n
  • Key Insight: The recurrence dp[i] = dp[i-1] + dp[i-2] only ever looks back 2 positions. The full array is therefore wasteful — we only need to track the last two values. This rolling-variable trick applies to any recurrence with a fixed lookback window.

This is the answer to give in an interview. The progression (naive → memo → dp → O(1)) demonstrates full depth of understanding.

Problem 2: House Robber

Link: LeetCode 198

Quick Summary: Given houses in a row with values, find the maximum sum where no two adjacent houses are selected.

Industry Context: This is the 1D variant of the maximum weighted independent set problem — a classic in resource scheduling. It models: task scheduling where adjacent tasks share a resource lock (you can’t run both), ad slot selection where adjacent slots on a webpage cannot both be filled (UI constraint), and antenna placement problems where adjacent antennas interfere.

Approach 1: Naive Recursion

// Time: O(2^n)  Space: O(n) stack
public static int robNaive(int[] nums) {
    return helper(nums, nums.length - 1);
}
 
private static int helper(int[] nums, int i) {
    if (i < 0) return 0;
    if (i == 0) return nums[0];
    return Math.max(nums[i] + helper(nums, i - 2),  // rob house i
                    helper(nums, i - 1));             // skip house i
}
  • Time: O(2
  • Space: O(n) stack
  • Tradeoff: Correct but exponential. helper(i-2) is recomputed by both the “rob i” and “skip i+1” branches — classic overlapping subproblems.

Recurrence: rob(i) = max(nums[i] + rob(i-2), rob(i-1))

The decision at each house: either rob it and skip the previous (nums[i] + rob(i-2)), or skip it and keep the best up through the previous house (rob(i-1)).

Approach 2: Memoization

// Time: O(n)  Space: O(n) memo + O(n) stack
public static int robMemo(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);
    return helper(nums, nums.length - 1, memo);
}
 
private static int helper(int[] nums, int i, int[] memo) {
    if (i < 0) return 0;
    if (i == 0) return nums[0];
    if (memo[i] != -1) return memo[i];
    memo[i] = Math.max(nums[i] + helper(nums, i - 2, memo),
                       helper(nums, i - 1, memo));
    return memo[i];
}
  • Time: O(n)
  • Space: O(n)

Approach 3: Bottom-Up DP

// Time: O(n)  Space: O(n) dp array
public static int robDP(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    return dp[n - 1];
}
  • Time: O(n)
  • Space: O(n)

Approach 4: Space-Optimized (Rolling Variables)

// Time: O(n)  Space: O(1)
public static int robOptimal(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int curr = Math.max(nums[i] + prev2, prev1);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}
  • Time: O(n)
  • Space: O(1)
  • Key Insight: The decision at house i only depends on the best result through house i-2 and i-1. Rolling two variables suffices. prev2 slides from dp[0] forward; prev1 is always the answer through the current house.

Watch the base case: dp[1] = max(nums[0], nums[1]) — for two houses you simply take the larger one. Not nums[1] alone! This is the most common off-by-one bug on this problem.

Problem 3: Longest Increasing Subsequence (LIS)

Link: LeetCode 300

Quick Summary: Find the length of the longest strictly increasing subsequence in an integer array. Elements need not be contiguous.

Industry Context: LIS is the backbone of diff algorithms and version-control systems — computing the minimum edit between two files reduces to finding LCS, and LCS reduces to LIS under certain transformations. The O(n log n) patience-sorting solution is also used in card-game AI and in database query optimizers for sequence-join reordering. Bioinformatics uses LIS to find the longest monotone chain of genomic annotations on a chromosome.

Approach 1: O(n²) DP

// Time: O(n^2)  Space: O(n)
public static int lisDP(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);    // each element is an LIS of length 1
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}
  • Time: O(n²) — for each of n positions, scan all previous positions
  • Space: O(n)
  • Key Insight: dp[i] = LIS length ending at index i. This state definition is critical: “ending at i” gives us the ability to extend subsequences consistently. If we defined dp[i] as “longest LIS in the first i elements”, the recurrence would be harder to write because we’d lose track of what value the subsequence ends on.

Recurrence written out:

dp[i] = 1 + max{ dp[j] : j < i AND nums[j] < nums[i] }
       = 1  if no such j exists (element stands alone)

Approach 2: O(n log n) — Patience Sorting with Binary Search

// Time: O(n log n)  Space: O(n)
public static int lisOptimal(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int num : nums) {
        // Binary search: leftmost position where tails[pos] >= num
        int lo = 0, hi = tails.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails.get(mid) < num) lo = mid + 1;
            else                       hi = mid;
        }
        if (lo == tails.size()) tails.add(num);   // extends LIS length
        else                    tails.set(lo, num); // replaces tail to stay small
    }
    return tails.size();
}
  • Time: O(n log n) — binary search over tails (size ≤ n) for each element
  • Space: O(n)
  • Key Insight (patience sorting):
    • tails[k] stores the smallest possible tail value of any increasing subsequence of length k+1 found so far.
    • A smaller tail is always better: it leaves more room for future elements to extend the subsequence.
    • When we encounter a new element x:
      • If x is larger than all tails → it extends the longest subsequence → tails.append(x), LIS length grows by 1.
      • Otherwise → it replaces the smallest tail that is >= x. This doesn’t change the current LIS length, but makes that length’s tail smaller, enabling more extensions later.
    • Important: tails is NOT the actual LIS, only a compact encoding that tracks the achievable lengths. Its final size equals the LIS length.
    • The binary search finds the insertion point in O(log n), giving the overall O(n log n) complexity.

This is the algorithm to know for senior interviews — it shows mastery beyond the textbook DP.

Problem 4: Coin Change

Link: LeetCode 322

Quick Summary: Given coin denominations (unlimited supply of each) and a target amount, find the minimum number of coins to make exact change. Return -1 if impossible.

Industry Context: This is the canonical unbounded knapsack problem. Production use cases: optimal denomination selection in digital payment systems (minimize transaction messages), resource bin-packing in cloud orchestrators (minimize containers needed to fit workloads), and compiler register allocation (minimize spills). The “BFS on implicit graph” interpretation is used in network routing — minimum hops from source to destination where each coin is an allowed step size.

Approach 1: Top-Down Memoization

// Time: O(amount × coins.length)  Space: O(amount)
public static int coinChangeMemo(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, Integer.MIN_VALUE);  // sentinel: uncomputed
    int result = helper(coins, amount, memo);
    return result == Integer.MAX_VALUE ? -1 : result;
}
 
private static int helper(int[] coins, int amount, int[] memo) {
    if (amount == 0) return 0;
    if (amount < 0)  return Integer.MAX_VALUE;
    if (memo[amount] != Integer.MIN_VALUE) return memo[amount];
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = helper(coins, amount - coin, memo);
        if (sub != Integer.MAX_VALUE) min = Math.min(min, sub + 1);
    }
    return memo[amount] = min;
}
  • Time: O(amount × |coins|)
  • Space: O(amount) — memo array; recursion depth is O(amount) in worst case

Recurrence:

coins(a) = 1 + min{ coins(a - c) : c ∈ coins, a - c >= 0 }
coins(0) = 0
coins(<0) = ∞

Approach 2: Bottom-Up DP

// Time: O(amount × coins.length)  Space: O(amount)
public static int coinChangeDP(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // "infinity" — more than any valid answer
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
  • Time: O(amount × |coins|)
  • Space: O(amount)
  • Key Insight: Fill dp left-to-right. dp[i] is defined as the minimum coins for amount i. At each amount, try every coin and ask: “if I use one of this coin, what was the best solution for the remainder?” The outer loop over amounts ensures dp[i - coin] is always already computed when we need it.
  • Why amount + 1 as infinity? The maximum coins you could ever need is amount (all 1-coins). Any answer larger than amount is therefore impossible — cleaner than Integer.MAX_VALUE which would overflow on + 1.

BFS graph interpretation: Treat each amount as a node; each coin denomination as an edge of weight 1. The answer is the shortest path from node 0 to node amount. The nested loops implement BFS-distance-filling without an explicit queue.

Problem 5: Word Break

Link: LeetCode 139

Quick Summary: Given a string s and a dictionary, determine if s can be segmented into one or more dictionary words.

Industry Context: This problem’s DP directly powers spell-checkers and autocorrect (can this character sequence be parsed into known words?), tokenization engines in NLP pipelines (used by every LLM tokenizer including BPE variants), URL slug parsing in web frameworks, and command-line argument parsing in shells where compound commands are split into known tokens. The BFS variant models how search engines crawl URL paths segment-by-segment.

Approach 1: Brute-Force Recursion

// Time: O(2^n)  Space: O(n) stack
public static boolean wordBreakNaive(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    return helper(s, dict, 0);
}
 
private static boolean helper(String s, Set<String> dict, int start) {
    if (start == s.length()) return true;
    for (int end = start + 1; end <= s.length(); end++) {
        if (dict.contains(s.substring(start, end)) && helper(s, dict, end))
            return true;
    }
    return false;
}
  • Time: O(2^n) — at each position, branch: take this prefix or extend it
  • Space: O(n)
  • Tradeoff: helper(s, dict, k) is called repeatedly with the same k from different paths — textbook overlapping subproblems.

Approach 2: Top-Down Memoization

// Time: O(n^2)  Space: O(n) memo + O(n) stack
public static boolean wordBreakMemo(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    Boolean[] memo = new Boolean[s.length()];  // null = uncomputed
    return helper(s, dict, 0, memo);
}
 
private static boolean helper(String s, Set<String> dict, int start, Boolean[] memo) {
    if (start == s.length()) return true;
    if (memo[start] != null) return memo[start];
    for (int end = start + 1; end <= s.length(); end++) {
        if (dict.contains(s.substring(start, end)) && helper(s, dict, end, memo)) {
            return memo[start] = true;
        }
    }
    return memo[start] = false;
}
  • Time: O(n²) — n starting positions × up to n substrings each (substring hashing is O(n), so strictly O(n³); practically treated as O(n²) with rolling hash)
  • Space: O(n)

Approach 3: Bottom-Up DP with Boolean Array

// Time: O(n^2)  Space: O(n) dp array
public static boolean wordBreakDP(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;    // empty prefix is always breakable
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}
  • Time: O(n²)
  • Space: O(n)
  • Key Insight: dp[i] = “can s[0..i-1] be broken into dictionary words?” For each position i, scan all split points j; if the prefix up to j is already breakable (dp[j]) AND the chunk s[j..i-1] is a dict word, then dp[i] is true. Base case dp[0] = true is the empty prefix — the “anchor” that allows the first word to be recognized.

State transition visualization:

s = "leetcode", dict = {"leet", "code"}
dp: [T, F, F, F, T, F, F, F, T]
         ^           ^         ^
         0           4         8
         j=0, i=4: dp[0]=T, "leet" in dict → dp[4]=T
         j=4, i=8: dp[4]=T, "code" in dict → dp[8]=T

Approach 4: BFS Approach

// Time: O(n^2)  Space: O(n) visited + O(n) queue
public static boolean wordBreakBFS(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    visited[0] = true;
    while (!queue.isEmpty()) {
        int start = queue.poll();
        for (int end = start + 1; end <= n; end++) {
            if (!visited[end] && dict.contains(s.substring(start, end))) {
                if (end == n) return true;
                visited[end] = true;
                queue.offer(end);
            }
        }
    }
    return false;
}
  • Time: O(n²)
  • Space: O(n)
  • Key Insight: Model positions 0..n as graph nodes and dictionary words as directed edges (j → i if s[j..i-1] is in the dict). The question becomes: is there a path from node 0 to node n? BFS answers this directly. This is exactly what the DP table computes, but made explicit as a graph traversal. In interviews, offering this alternative perspective signals strong pattern recognition.

No space optimization is applicable here — Word Break’s dp[i] can depend on any dp[j] for j < i, not just the last 1 or 2 cells.

Top-Down vs Bottom-Up Comparison

DimensionTop-Down (Memoization)Bottom-Up (Tabulation)
Code structureRecursive — mirrors the recurrence directlyIterative — explicit loop order
Subproblem orderComputed on-demand (lazy)Computed in fixed order (eager)
Stack overheadYes — O(n) or O(depth) call stackNo — O(1) per iteration
Stack overflow riskYes for large n (Java default ~500–1000 frames)None
Easier to implement firstUsually — just add a cache to the recursionRequires knowing the fill order upfront
Space optimizationHarder — cache must hold all reachable statesEasy — slide a window over the array
Handles sparse subproblemsYes — only computes reachable statesNo — fills entire table even if most cells unused
DebuggingEasier — add prints to the recursive functionHarder — state is all in the array
Interview preferenceExcellent starting point; show you can convertOptimal final answer; cleaner asymptotically

Recommendation: In interviews, start with top-down memoization to prove correctness quickly, then convert to bottom-up to optimize space. State this plan explicitly — it demonstrates seniority.

Key Takeaways

How to Recognize DP Problems in Interviews

  • The problem asks for a count, maximum, minimum, or yes/no over an exponentially large search space.
  • A recursive formulation naturally arises but results in the same sub-call being made multiple times with identical arguments (“overlapping subproblems”).
  • Removing an element from the end (or beginning) of the input produces a strictly smaller subproblem of the same type (“optimal substructure”).
  • Keywords: “number of ways”, “minimum cost”, “maximum profit”, “can you reach”, “longest/shortest subsequence”, “partition”, “segment”.
  • The brute-force is a decision tree with exponential branching — each decision independent of future decisions given the current state.

The Two DP Prerequisites

  1. Overlapping Subproblems: The same sub-computation appears in multiple branches of the recursive solution. If subproblems are all distinct (as in merge sort), memoization adds no benefit — use divide and conquer instead.

  2. Optimal Substructure: An optimal solution to the whole problem contains optimal solutions to its subproblems. If a local choice can invalidate a globally optimal path (as in some greedy pitfalls), DP may still work but requires careful state design.

Quick test in an interview: Draw the recursion tree for a small input (n=4 or n=5). If the same node appears more than once, DP applies.

Common 1D DP Patterns

PatternArchetypeKey StateSpace
Fibonacci / Path countingClimbing Stairsdp[i] = ways to reach iO(1) after optimization
Decision at each stepHouse Robberdp[i] = best through index iO(1) after optimization
Sequence DP (LIS/LCS style)LISdp[i] = best ending at iO(n) — can’t reduce (any j < i may matter)
Unbounded KnapsackCoin Changedp[i] = best for target iO(target) — no item dimension needed
String segmentationWord Breakdp[i] = reachable from s[0..i-1]O(n)
0/1 Knapsack(2D DP — see Session 10)dp[i][w] = best using first i items, capacity wO(n × W) or O(W)

Common DP Pitfalls for Senior Interviews

  • Wrong state definition: If your recurrence requires information not captured in your state, redesign the state before writing code. “I’ll handle it in the transition” is usually wrong.
  • Missing base cases: Always handle: empty input, size-1 input, and the “impossible” sentinel (use Integer.MAX_VALUE - 1 not MAX_VALUE to avoid overflow on +1).
  • Integer overflow: dp[i] + 1 where dp[i] = Integer.MAX_VALUE wraps around. Guard with if (sub != Integer.MAX_VALUE) before adding.
  • Off-by-one in dp size: If dp[i] represents the answer for the first i elements, your array needs dp[0..n] (size n+1). Draw the table on paper first.
  • Forgetting break in Word Break DP: Once dp[i] is set to true, break the inner loop — otherwise you waste time on remaining split points.
  • LIS: O(n log n) tails array is NOT the LIS sequence: It’s a monotone bookkeeping array. To reconstruct the actual LIS, you need a separate parent-tracking array.

System Design Connections

  • Coin Change → Cache admission policy: Belady’s optimal page-replacement algorithm is an offline DP — given future access patterns, which pages to evict to minimize misses. Online approximations (LRU, LFU) are heuristics for the same optimization objective.
  • Word Break → Tokenizer design: BPE (Byte-Pair Encoding) tokenizers in GPT/LLaMA use a greedy variant of Word Break; Viterbi decoding in HMMs is the probabilistic generalization of this DP.
  • LIS → Version control diff: Git’s diff algorithm is based on the patience diff algorithm, which is an application of LIS on line hashes. Every git diff you run uses this O(n log n) structure.
  • House Robber → Task scheduling with conflict windows: Weighted interval scheduling (maximize total weight of non-overlapping intervals) generalizes House Robber to arbitrary intervals; its DP solution is the algorithm behind calendar conflict resolution and CPU burst scheduling.
  • Climbing Stairs → Probabilistic automata: Counting paths through a DAG (the generalized form of climbing stairs) is the core computation in probabilistic context-free grammars, Markov chain analysis, and network reliability calculations in distributed systems.

Graph View

Backlinks