Unit 3: Dynamic Programming - Subjective Questions

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

A problem is suitable for dynamic programming when it has the following properties:

• Optimal substructure: An optimal solution to the problem can be constructed from optimal solutions to its subproblems.
• Overlapping subproblems: The same subproblems occur repeatedly during computation.
• State representation: Each subproblem can be represented using a small set of parameters called a state.
• Recurrence relation: The solution of a state can be expressed in terms of solutions to smaller states.
• Base cases: The smallest subproblems have directly known solutions.

DP avoids repeated computation and often converts an exponential-time recursive algorithm into a polynomial-time algorithm.

The three techniques differ in how they divide problems and construct solutions:

Key distinction:

• Dynamic programming evaluates and stores solutions to repeated subproblems.
• Divide-and-conquer recursively solves independent subproblems.
• A greedy algorithm makes an irreversible locally optimal decision at each step.

Top-down memoization:

• Begins with the original problem and recursively solves required subproblems.
• Stores each computed result in a cache.
• Before solving a subproblem, the cache is checked.
• Only subproblems actually needed are evaluated.

Bottom-up tabulation:

• Begins with the smallest subproblems.
• Uses an iterative order so that prerequisite states are computed first.
• Stores results in a table until the original problem is solved.

Comparison:

Both approaches normally have the same asymptotic time and space complexity when they evaluate the same set of states.

The binomial coefficient is defined as

Using Pascal's identity, the recurrence is

with base cases

A bottom-up algorithm fills a table for and .

Procedure:

1. Set for every .
2. Set whenever .
3. For the remaining entries, use .
4. Return .

Complexity:

• Time complexity:
• Space complexity with a two-dimensional table:
• Space complexity using one row:

This is more efficient than the direct recursive implementation, which repeatedly computes the same coefficients.

Using Pascal's recurrence,

The required values up to are:

Therefore,

Space optimization:

Only the previous row is needed to generate the next row. A single array of size can therefore be used. Its entries must be updated from right to left:

Right-to-left updating prevents a newly modified value from being reused in the same iteration. The optimized algorithm uses space and time.

A memory function is a top-down dynamic programming technique in which the result of each solved subproblem is stored so that it is not computed again. It is also called memoization.

Suppose a problem is represented by

A memory function operates as follows:

1. Create a table and mark every state as not computed.
2. When is requested, first inspect the table.
3. If the value is already stored, return it immediately.
4. Otherwise, recursively evaluate the required smaller states.
5. Compute , store it in the table, and return it.

Advantages:

• Prevents repeated evaluation of overlapping subproblems.
• Preserves the natural recursive formulation.
• May avoid computing table entries that are never required.

If there are distinct states and each state requires work excluding recursive calls, the total time is generally .

The ordinary recursive definition is

with

A direct recursive algorithm repeatedly computes values such as and , resulting in exponential running time.

With a memory function:

• An array is initialized as not computed.
• Before evaluating , the algorithm checks .
• If is available, it is returned.
• Otherwise, and are computed, and their sum is stored in .

Each value is computed at most once.

Complexity:

• Direct recursion: approximately time and recursion depth.
• Memoized recursion: time.
• Memoized space: for the cache and for the recursion stack.

Thus, memoization changes the computation from exponential time to linear time.

In the knapsack problem, there are items. Item has weight and value . The knapsack capacity is . Each item may be selected either once or not at all.

Define as the maximum value obtainable using the first items with capacity .

The base cases are

and

The recurrence is

The two alternatives are:

• Exclude item : value .
• Include item : value .

The answer is stored in .

Complexity:

• Time:
• Space: , reducible to

The running time is pseudo-polynomial because it depends on the numeric capacity rather than only on the number of input bits.

Let denote the maximum value using the first items and capacity .

The completed table is:

For the final item, the two choices at capacity are:

• Exclude it: .
• Include it: .

Hence,

The optimal selection consists of:

• Item : weight , value
• Item : weight , value

Their total weight is and total value is . Therefore, the optimal knapsack value is .

knapsack:

• Each item is either selected completely or not selected.
• Items cannot be divided.
• Dynamic programming can solve it in pseudo-polynomial time.
• Choosing the highest value-to-weight ratio first is not always optimal.

Fractional knapsack:

• Any fraction of an item may be selected.
• Sorting by decreasing ratio and filling the knapsack greedily is optimal.
• Its typical complexity is because of sorting.

Why greedy fails for knapsack:

A high-ratio item may occupy capacity that could otherwise hold a combination of lower-ratio items having a greater total value. Since an item cannot be divided, an early greedy selection can prevent the global optimum.

Dynamic programming avoids this issue by evaluating both possibilities for every item:

• Excluding the item
• Including the item when capacity permits

Thus, the restriction destroys the general greedy-choice property.

The matrix-chain multiplication problem determines the parenthesization of a matrix product that minimizes the number of scalar multiplications. The order of matrices cannot be changed.

Suppose matrix has dimensions . Define as the minimum number of scalar multiplications required to compute

The base case is

because a single matrix requires no multiplication.

If the chain is split between and , the cost is

Therefore,

A second table stores the value of that gives the minimum, allowing the optimal parenthesization to be reconstructed.

Complexity:

• Time:
• Space:

There are two possible parenthesizations.

1.

The cost of multiplying and is

The result has dimensions . Multiplying it by costs

Hence, the total cost is

2.

The cost of multiplying and is

The result has dimensions . Multiplying it by costs

Hence, the total cost is

Since , the optimal parenthesization is

and the minimum number of scalar multiplications is .

During the matrix-chain dynamic programming algorithm, a split table is maintained. It stores the split position that minimizes the multiplication cost for the subchain .

To reconstruct the parenthesization:

• If , output .
• Otherwise, retrieve .
• Output a left parenthesis.
• Recursively reconstruct the subchain .
• Recursively reconstruct the subchain .
• Output a right parenthesis.

The recursive rule can be written as

The cost table gives the minimum cost, whereas the split table provides the decisions needed to construct the actual optimal solution. Reconstruction takes time because the final parenthesization contains all matrices.

A subsequence is obtained by deleting zero or more elements from a sequence without changing the order of the remaining elements. The longest common subsequence (LCS) of two sequences is a common subsequence of maximum length.

Let

Define as the LCS length of prefixes and .

The base cases are

The recurrence is

If the current symbols match, they can extend an LCS of the preceding prefixes. If they do not match, one of the two symbols must be excluded.

Complexity:

• Time:
• Space:
• If only the length is needed, space can be reduced to .

The dynamic programming table is filled using

For the complete sequences, the final table entry is

One LCS can be obtained by tracing backward from :

• Select matching symbols when the current entry was obtained diagonally.
• Otherwise, move toward an adjacent cell having the same value.
• Reverse the collected symbols after reaching the first row or column.

One resulting LCS is

Another valid LCS is

Thus, the LCS is not necessarily unique, but every longest common subsequence in this example has length .

Reconstructing an LCS:

Starting at :

1. If , include that symbol in the LCS and move diagonally to .
2. If and , move upward.
3. Otherwise, move left.
4. Continue until or .
5. Reverse the collected symbols because they were discovered from the end to the beginning.

If the upper and left entries are equal, either direction may produce a valid LCS. Exploring both directions may reveal multiple LCSs.

Subsequence versus substring:

• A subsequence preserves relative order, but its elements need not be contiguous. For example, is a subsequence of .
• A substring must consist of contiguous elements. For example, is a substring of .

Therefore, the longest common substring problem uses a different recurrence from the LCS problem.

An optimal binary search tree (OBST) is a binary search tree constructed from ordered keys so that the expected search cost is minimum, given the access probabilities or frequencies of the keys.

If key has successful-search probability and is stored at depth , its contribution to the expected number of comparisons is proportional to

When unsuccessful searches are included, dummy keys with probabilities also contribute to the expected cost.

A height-balanced tree minimizes or controls tree height, but it does not consider how frequently individual keys are searched. If some keys are accessed much more often, placing them near the root may lower the average search cost even if the resulting tree is not perfectly balanced.

Thus:

• A balanced BST focuses mainly on worst-case depth.
• An OBST focuses on probability-weighted average search cost.
• Dynamic programming examines every possible root for each interval of ordered keys.

Let the ordered keys be , with successful-search frequencies .

Define as the minimum weighted search cost of an optimal BST containing keys through . Let

If is selected as the root, then:

• Keys through form the left subtree.
• Keys through form the right subtree.
• Every key in both subtrees moves one level deeper, adding to the weighted cost.

Therefore,

The empty-tree base case is

For a single key,

Intervals are evaluated in increasing order of length. A root table stores the minimizing value of for reconstruction.

Complexity:

• Standard time complexity:
• Space complexity:

Let the ordered actual keys be .

• is the probability of successfully searching for key .
• is the probability of an unsuccessful search in the gap represented by dummy key , where .

Define:

• : minimum expected cost for keys through .
• : total probability in that subtree.

The base cases are

The weight recurrence is

If is chosen as the root, the expected cost is

Hence,

The additional term appears because all nodes in the left and right subtrees move one level deeper when attached below the root. The minimizing roots are stored to reconstruct the optimal tree.

While computing the minimum expected costs, a table stores the key index selected as the root of the optimal subtree containing keys through .

Reconstruction procedure:

1. Start with the complete interval .
2. Set as the root of the entire tree.
3. Recursively construct the left subtree from interval .
4. Recursively construct the right subtree from interval .
5. For an empty interval, attach the appropriate dummy key if unsuccessful searches are represented.

In general, for an interval :

• If , it represents an empty subtree.
• Otherwise, choose .
• Build the left subtree from and the right subtree from .

Complexity:

• Filling the standard DP tables: time.
• Cost, weight, and root tables: space.
• Reconstructing the final tree: time.

The cost table identifies the minimum expected cost, while the root table preserves the structural decisions required to build the actual tree.