Unit 4: Basic Dynamic Programming - Subjective Questions

Dynamic Programming (DP) is an algorithmic technique used to solve problems by dividing them into smaller subproblems, solving each subproblem only once, and storing its result for future use.

The two essential properties are:

• Optimal substructure: The optimal solution to the complete problem can be constructed from optimal solutions of its subproblems.
• Overlapping subproblems: The same smaller subproblems occur repeatedly during the solution process.

The general DP approach is:

1. Define the state representing a subproblem.
2. Establish a recurrence or state transition.
3. Specify base cases.
4. Compute and store the results.
5. Construct the final answer from the stored values.

The Fibonacci sequence is defined as:

with base cases:

A direct recursive solution repeatedly calculates the same values, resulting in exponential time complexity of approximately .

Using dynamic programming, each Fibonacci value is calculated once and stored:

• dp[0] = 0
• dp[1] = 1
• dp[i] = dp[i-1] + dp[i-2] for

The time complexity is because there are states. The space complexity is when an array is used. Since only the previous two values are required, the space can be optimized to .

The three approaches differ as follows:

• Simple recursion:

  • Uses the mathematical recurrence directly.
  • Recomputes the same subproblems many times.
  • Time complexity is .
  • Space complexity is because of the recursion stack.

• Memoization:

  • Uses a top-down recursive approach.
  • Stores each computed value in a table.
  • Time complexity is .
  • Space complexity is for the table and recursion stack.

• Tabulation:

  • Uses a bottom-up iterative approach.
  • Starts from the base cases and builds the answer progressively.
  • Time complexity is .
  • Space complexity is , or with space optimization.

Memoization is often easier to formulate recursively, whereas tabulation generally avoids recursion overhead and stack-depth limitations.

In the tiling problem, a board must be completely covered using tiles without overlapping or leaving uncovered cells.

For a board using dominoes, consider the first column:

• If it is covered by one vertical domino, the remaining board is .
• If it is covered by two horizontal dominoes, the remaining board is .

Therefore, the recurrence is:

The base cases are:

Thus, the number of tilings follows the Fibonacci pattern. A bottom-up DP solution computes each value once in time and uses space, or space after optimization.

Let represent the number of ways to tile a board using dominoes.

To determine the arrangement at the leftmost column, there are only two possibilities:

• Vertical placement: One vertical domino fills the first column. The remaining board has width , contributing arrangements.
• Horizontal placement: A horizontal domino occupies the upper cell of the first column. To avoid leaving the lower cell uncovered, another horizontal domino must occupy the lower cell. The remaining board has width , contributing arrangements.

The two cases are mutually exclusive and cover all possible arrangements. Therefore:

The base cases are and . The empty board has one valid arrangement, and a board of width one can be covered in exactly one way.

Let denote the number of distinct ways to reach the th stair.

The last move can be either:

• A one-step move from stair .
• A two-step move from stair .

Hence, the recurrence is:

Suitable base cases are:

The value represents one way to reach the ground, namely doing nothing. A bottom-up algorithm initializes the base values and computes values up to .

The time complexity is and the space complexity is , which can be reduced to because only the previous two values are needed.

Let be the number of ways to reach stair . The final move can have length one, two, or three.

Therefore, the state transition is:

A convenient set of base cases is:

For , the possibilities are two one-step moves or one two-step move. For larger values, each valid sequence must end with one of the three possible step sizes.

The DP algorithm calculates the values from through . It takes time. With a table, it takes space, but the space can be reduced to by retaining only the previous three values.

Memoization and tabulation are two methods for storing results of subproblems.

Memoization begins with the original problem and recursively solves smaller states. Tabulation begins with base cases and builds toward the final state.

Both approaches commonly achieve the same asymptotic complexity, but their practical performance and memory behavior may differ.

A state is a compact representation of a subproblem. It contains enough information to determine the answer for that subproblem.

A state transition describes how the answer for one state can be obtained from answers to other states.

For the climbing stairs problem:

• State definition: is the number of ways to reach stair .
• State transition: The last move reaches stair from either or .

Thus:

• Base cases: and .
• Final answer: .

A correct state should avoid storing unnecessary information while preserving all information required for future transitions.

The optimal substructure property states that an optimal solution to a problem contains optimal solutions to its subproblems.

This property is important because dynamic programming constructs a global solution by combining solutions of smaller states. If a subproblem were solved non-optimally, the final solution might also be non-optimal.

For example, in a minimum-cost path problem, suppose the cheapest path from source to destination passes through vertex . The portion from to must itself be a minimum-cost path. Otherwise, replacing it with a cheaper path would produce a cheaper path from to , contradicting optimality.

Without optimal substructure, storing only the best result for each state may discard information needed to construct the global optimum.

The overlapping subproblems property exists when a problem recursively generates the same smaller subproblems multiple times.

For Fibonacci numbers:

Computing requires and . Computing again requires and . Therefore, and other smaller values are calculated repeatedly.

This repeated work causes the simple recursive algorithm to have exponential time complexity. Dynamic programming eliminates the repetition by storing each computed value. Once is known, every later reference uses the stored result.

Overlapping subproblems alone is not sufficient for every DP solution; the problem should generally also have optimal substructure or an equivalent compositional structure.

A systematic dynamic programming process consists of the following steps:

1. Identify the subproblems: Determine how the original problem can be divided into smaller instances.
2. Define the state: Specify what each DP entry represents.
3. Find the transition: Express a state in terms of previously solved states.
4. Set the base cases: Handle the smallest valid inputs explicitly.
5. Choose an evaluation method: Use memoization or tabulation.
6. Determine the computation order: Ensure that every required predecessor state is available.
7. Compute the final result: Read the answer from the target state.
8. Optimize space if possible: Retain only the states needed for future transitions.
9. Verify the solution: Test base cases, small inputs, boundary conditions, and expected complexity.

This process prevents common errors such as incomplete states, incorrect initialization, and invalid transition dependencies.

To formulate a DP problem, follow these steps:

• Identify the decision or position: Determine what changes as the problem progresses.
• Define a state: Let the state describe a subproblem using the smallest sufficient information.
• Analyze the final choice: Consider the possible actions that could lead to the current state.
• Write the transition: Combine the results of predecessor states.
• Define base cases: Specify answers for the smallest states.
• Identify the target state: Determine which state contains the requested answer.

For climbing stairs:

• State: represents the number of ways to reach stair .
• Final move: One step or two steps.
• Transition: .
• Base cases: and .
• Target: .

The formulation is correct because every valid path to stair ends with exactly one of the allowed final moves.

A bottom-up algorithm computes the smallest values first and stores them in an array.

Fibonacci(n):
    if n == 0:
        return 0
    create dp[0..n]
    dp[0] = 0
    dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

The table entries have the meaning . The loop is valid because and have already been calculated before .

• Time complexity: .
• Space complexity: .
• Space-optimized complexity: by storing only the two previous values.

The algorithm avoids the repeated computations present in simple recursion.

Let ways(i) represent the number of ways to reach stair . The recursive definition is:

A memoized algorithm is:

ways(i):
    if i == 0 or i == 1:
        return 1
    if memo[i] is already computed:
        return memo[i]
    memo[i] = ways(i - 1) + ways(i - 2)
    return memo[i]

The memo table ensures that each state is evaluated only once. Without memoization, the same states would be recomputed many times.

• Number of states: .
• Work per state: .
• Time complexity: .
• Space complexity: for the memo table and recursion stack.

The method is top-down because it begins with the requested state and explores only states needed to solve it.

Consider the recurrence:

In naive recursion, the same subproblems are repeatedly solved. The recursion tree grows exponentially, so the time complexity is in the usual analysis. The recursion depth is , giving auxiliary stack space.

In dynamic programming, each state from through is computed once. Therefore:

• Time complexity is .
• Space complexity is with a full DP table.
• Space complexity can become when only the previous two states are needed.

Dynamic programming improves time complexity by trading additional storage for reuse of previously computed results.

Dynamic programming problems can have different objectives:

• Counting problems: Compute the number of valid solutions. The transition usually combines alternatives using addition.
• Optimization problems: Find the minimum or maximum value among possible choices. The transition usually uses min or max.

Examples from this unit include:

• Fibonacci and climbing stairs are counting or sequence-value problems, depending on the interpretation.
• The tiling problem counts the number of valid tile arrangements.
• A minimum-cost version of a stairs or tiling problem would be an optimization problem.

For a counting problem:

For an optimization problem:

The state-definition process is similar, but the operation used to combine choices depends on the required objective.

Common DP optimization techniques include:

• Memoization: Cache results in a top-down recursive solution to avoid repeated work.
• Tabulation: Use an iterative table to compute states in dependency order.
• Rolling-array optimization: Store only the previous states required by the transition.
• State reduction: Remove unnecessary dimensions or information from the state.
• Sparse storage: Store only states that are actually reachable when the state space is large and sparse.
• Early termination: Stop processing when a valid condition guarantees that further computation is unnecessary.

For Fibonacci and two-step climbing stairs, the transition depends only on the previous two states. Instead of storing all values, maintain variables such as previousTwo and previousOne. This reduces space from to while preserving time complexity.

The standard tabulation recurrence is:

To calculate , only and are required. Earlier values will never be referenced again. Therefore, the complete table can be replaced by two variables.

previousTwo = 0
previousOne = 1
for i from 2 to n:
    current = previousTwo + previousOne
    previousTwo = previousOne
    previousOne = current
return previousOne

The algorithm maintains the invariant that before each iteration, previousTwo and previousOne contain the two most recent Fibonacci values.

• Time complexity: .
• Space complexity: .

The optimization is valid because the state transition has a fixed dependency window of size two.

Common errors include:

• Incorrect base cases: For example, confusing in Fibonacci with in counting problems such as stairs and tiling.
• Incomplete state definition: Failing to specify exactly what a DP entry represents.
• Missing cases in the transition: Omitting one of the possible final moves or tile placements.
• Double-counting arrangements: Treating the same tiling or step sequence as different when it is not.
• Wrong iteration order: Using a state before it has been computed in tabulation.
• Off-by-one errors: Mixing zero-based indexing with one-based stair numbering.
• Unnecessary memory usage: Storing the entire table when only a few previous states are needed.
• Ignoring boundary inputs: Failing to handle , , or values smaller than the largest allowed move.

Testing small cases manually often reveals incorrect initialization or transitions.