Unit 5: Dynamic Programming Problems - Subjective Questions

Dynamic programming (DP) is an algorithmic technique that solves a problem by dividing it into smaller overlapping subproblems, solving each distinct subproblem once, and storing its result for reuse.

A problem is suitable for DP when it has these properties:

• Optimal substructure: An optimal solution to the complete problem can be constructed from optimal solutions to its subproblems. For example, an LCS ending at positions and depends on an LCS of smaller prefixes.
• Overlapping subproblems: A recursive solution repeatedly evaluates the same subproblems. DP avoids this repeated work by caching results.

The two common implementation styles are:

• Memoization: A top-down recursive approach that stores computed results.
• Tabulation: A bottom-up iterative approach that fills a table in dependency order.

DP commonly reduces exponential recursive algorithms to polynomial time, usually at the cost of additional memory.

For an array , define as the length of the longest strictly increasing subsequence that ends at index .

Initialization:

• Every single element is an increasing subsequence, so for all .

Transition:

For each pair , if , element can extend the subsequence ending at :

Final result:

For example, for , an LIS is , so the answer is .

• Time complexity:
• Space complexity:

A predecessor array can also be maintained to reconstruct an actual LIS.

Maintain an array , where stores the smallest possible ending value of an increasing subsequence of length found so far.

For every value in the input:

• Find the first position such that using binary search.
• Replace with .
• If no such position exists, append to .

At the end, the length of is the LIS length. Keeping the smallest tail gives future values the greatest opportunity to extend a subsequence.

The values in may come from incompatible positions in the input because replacements only preserve the best tail value for each length. Therefore, is not guaranteed to be an actual subsequence. To reconstruct an LIS, predecessor indices and the source index of each tail must also be recorded.

• Time complexity:
• Space complexity:

Given sequences and , the Longest Common Subsequence is the longest sequence that appears in both and in the same relative order, but not necessarily contiguously.

Let denote the LCS length of prefixes and .

Base cases:

Recurrence:

• If , the matching character extends an LCS of the smaller prefixes:

• Otherwise, one of the two final characters must be excluded:

The required length is .

• Time complexity:
• Space complexity: , reducible to when only the length is required.

Start at the bottom-right cell and backtrack toward .

• If , include that character in the answer and move diagonally to .
• If the characters differ and , move upward to .
• Otherwise, move left to .
• Stop when or .
• The characters are collected in reverse order, so reverse them at the end.

If the upper and left cells have equal values, either direction may produce a valid LCS. Different choices can produce different LCS strings of the same maximum length.

Backtracking takes time in the worst case after the table has been constructed.

A substring or contiguous subarray consists of consecutive elements from the original sequence. A subsequence is formed by deleting zero or more elements while preserving the relative order of the remaining elements.

For the sequence :

• is both a contiguous subarray and a subsequence.
• is a subsequence and is also contiguous here.
• is a subsequence but not a contiguous subarray because the value is skipped.

LIS and LCS permit skipped elements, so they search for subsequences, not contiguous segments. Requiring contiguity changes both the recurrence and the answer. For example, longest common substring DP resets a cell to zero after a mismatch, while LCS DP takes the maximum of neighboring states.

The binomial coefficient counts the ways to choose objects from objects. Pascal's identity gives the recurrence:

The base cases are:

A table can be filled row by row for and . Each entry represents choosing or not choosing a particular object.

A one-dimensional implementation initializes and processes each row from right to left:

Right-to-left iteration is essential because it prevents values from the current row from overwriting values still needed from the previous row.

• Time complexity:
• Space complexity:

This approach avoids factorial overflow occurring before division, although the coefficient itself can still require arbitrary-precision arithmetic or modular arithmetic.

In the Box Stacking problem, boxes are stacked to maximize total height, subject to the rule that both base dimensions of an upper box must be strictly smaller than the corresponding dimensions of the lower box.

For each box with dimensions , generate its three orientations by choosing each dimension as height. Normalize each base so that its first dimension is at least its second. Thus, an orientation is represented as .

Sort all orientations by decreasing base area or another order consistent with checking possible lower boxes before upper boxes. Define as the maximum stack height with orientation at the top or bottom, according to the chosen ordering. A common transition is:

for every earlier orientation whose base satisfies and . If none exists, .

The answer is . With orientations, the standard solution takes time and auxiliary space after sorting.

Two details are necessary for a correct Box Stacking implementation:

• Strict comparisons: An upper box can be placed only when both of its base dimensions are strictly smaller than those of the lower box. The condition is and . Using only base area or allowing equality may create physically invalid stacks.
• Orientation normalization: For every orientation, store the larger base side first, such as and . This gives a consistent representation and makes pairwise comparisons reliable.

Base area is useful for sorting, but area alone does not prove that one rectangle fits on another. For example, a base has area , but it does not fit on a base even though the latter has area . Both dimensions must therefore be checked explicitly.

Suppose item has weight , value , and capacity is . Because duplicates are forbidden, each item can be selected at most once.

Let be the maximum value obtainable using the first items with capacity .

Base cases:

Transition:

• If , item cannot be selected:

• Otherwise, choose the better of excluding and including it:

The answer is .

• Time complexity:
• Space complexity: , reducible to

The algorithm is pseudo-polynomial because its running time depends on the numeric capacity , not merely on the number of bits used to represent .

In 0/1 Knapsack, each item may be selected at most once. In Unbounded Knapsack, any item may be selected repeatedly.

For both variants, a one-dimensional state can store the best value at capacity . Their update directions differ:

• 0/1 Knapsack: Process capacities from down to . Descending order ensures that still belongs to the state before item was considered, preventing duplicate use.
• Unbounded Knapsack: Process capacities from up to . Ascending order permits a state updated using item to be reused, allowing multiple copies.

The 0/1 update is:

A wrong iteration direction silently changes the problem being solved. Both algorithms take time and space.

The edit distance or Levenshtein distance between strings and is the minimum number of single-character insertions, deletions, and replacements required to transform into .

Let denote the edit distance between prefixes and .

Base cases:

If :

Otherwise:

The three terms correspond respectively to deletion, insertion, and replacement. The result is .

• Time complexity:
• Space complexity: , reducible to if the edit sequence itself is not required.

The edit distance between kitten and sitting is . One optimal transformation is:

• Replace k with s: kitten becomes sitten.
• Replace e with i: sitten becomes sittin.
• Insert g at the end: sittin becomes sitting.

Thus, two replacements and one insertion are required.

In the DP table, the top row and left column are initialized with prefix lengths. Every remaining cell takes either the diagonal value when characters match or one plus the minimum of the deletion, insertion, and replacement predecessor cells when they differ. The bottom-right table entry is , proving that no sequence using fewer than three allowed edits exists.

Given matrices , where has dimensions , Matrix Chain Multiplication finds the parenthesization requiring the fewest scalar multiplications. Matrix order cannot be changed; only grouping can change.

Let be the minimum cost of multiplying matrices through .

Base case:

For , try every final split position where :

The final term is the cost of multiplying the two resulting matrices. Fill the table by increasing chain length so that shorter subchains are available first.

• Time complexity:
• Space complexity:

A separate split table stores the best for reconstructing the optimal parenthesization.

Let the matrices be , , and . There are two parenthesizations.

Option 1:

• Multiply :
• The result is . Multiply it by :
• Total cost:

Option 2:

• Multiply :
• The result is . Multiply by it:
• Total cost:

Therefore, the optimal parenthesization is , with scalar multiplications.

The Balanced Partition Problem divides a set of non-negative integers into two subsets such that the absolute difference between their sums is minimized.

Let the total sum be . If one subset has sum , the other has sum , and the difference is:

Therefore, it is sufficient to find the largest reachable subset sum satisfying .

Use a Boolean DP array where indicates whether sum can be formed. Initialize . For every value , update in descending order:

Finally, scan downward from $\lfloor S/2
floor$ for the first reachable $s$. The minimum difference is $S-2s$.

• Time complexity:
• Space complexity:

The descending update ensures each input element is used at most once.

The total sum is:

The target is to find a reachable subset sum as close as possible to:

The sum is reachable directly using the element . The remaining elements form the other subset with sum :

• First subset: , sum
• Second subset: , sum

The minimum difference is:

A difference of is impossible because the total sum is odd. Hence, is optimal.

Memoization is top-down:

• It begins with the original problem and recursively evaluates required subproblems.
• Results are stored in a cache.
• It may avoid states that are never needed.
• It has recursion overhead and may overflow the call stack for deep state graphs.

Tabulation is bottom-up:

• It determines a dependency order and fills states iteratively.
• It avoids recursion overhead and usually has predictable memory access.
• It often computes every state, including some that may not be required.
• It makes space optimization easier when only earlier rows or columns are needed.

For LCS and Edit Distance, table rows can be filled from smaller prefixes. For Matrix Chain Multiplication, intervals must be processed by increasing length. Both methods implement the same recurrence and should have the same asymptotic state-transition cost when they evaluate the same states.

Space can be reduced when each state depends on only a limited part of the DP table.

• LCS: Each cell depends on the previous row and the current row. Store two rows, reducing space from to . With careful variable management, one row is also possible.
• Edit Distance: Its cells likewise depend on the previous row, current row, and previous diagonal value, so space becomes .
• 0/1 Knapsack: Store one array of capacities and update it from high capacity to low capacity, reducing space to .

This direct optimization should be avoided when the full table is needed to reconstruct an LCS, edit script, or selected set of knapsack items. Reconstruction then requires retained decisions, a full table, recomputation, or a more advanced divide-and-conquer technique. Space optimization must also preserve update order; otherwise, overwritten values can change the recurrence.

Common pitfalls include:

• LIS: Using instead of when the required subsequence is strictly increasing; returning only instead of the maximum over all endpoints.
• LCS: Confusing subsequences with substrings; mishandling empty-prefix base cases; losing information needed for reconstruction during space optimization.
• 0/1 Knapsack: Updating one-dimensional capacities in ascending order, which permits the same item to be used repeatedly.
• Matrix Chain Multiplication: Multiplying incompatible dimension terms, changing matrix order, or filling intervals before their smaller subintervals are available.
• Balanced Partition: Searching beyond unnecessarily; updating sums in ascending order and thereby reusing an element.
• General DP: Choosing an incomplete state definition, omitting base cases, using an invalid evaluation order, or allowing numeric overflow in costs, sums, and counts.

Correct DP design requires a precise state meaning, a justified recurrence, complete base cases, and an evaluation order consistent with dependencies.