Template for solving Dynamic Programming problems

Here is a general Top-Down Dynamic Programming (Memoization) template in pseudo code:

Pseudo Code Template:

// Initialize memoization table (can use a dictionary, array, or other structures)
Memo = {}

Function TopDown(State):
    // Check if the result for this state has already been computed
    if State is in Memo:
        return Memo[State]

    // Base case: return a result for the simplest subproblem (if applicable)
    if State is a base case:
        return BaseCaseValue

    // Recursive case: solve subproblems
    Result = INF   // Initialize result with a large number or a worst-case value

    // Loop through each possible action/choice
    for each option in problem:
        // Update the state based on the action/choice
        NewState = ApplyOption(State, option)

        // Recursively solve the subproblem and combine results
        SubResult = TopDown(NewState)

        // Use the subresult to update the current result
        Result = CombineResult(Result, SubResult)

    // Store the computed result in the memoization table for future reference
    Memo[State] = Result

    return Result

// Main function to start the top-down DP process
Function Main():
    // Define the initial state
    InitialState = DefineInitialState()

    // Call the TopDown function starting from the initial state
    FinalResult = TopDown(InitialState)

    // Output the final result
    Print(FinalResult)

Explanation:

Memoization Table:
The Memo table stores the results of previously computed states to avoid redundant calculations. It can be an array, dictionary, or hash map.
Base Case:
The function checks for a base case that directly returns the result without further recursion (e.g., a simple subproblem like a single item, a base condition like n = 0 in a Fibonacci problem).
Recursive Case:
The main computation involves breaking the problem into subproblems. For each action or decision, the state is updated, and the subproblem is solved recursively. The results are then combined (e.g., adding or taking the minimum/maximum).
Memoization:
After solving the subproblem, the result is stored in the memo table (Memo[State] = Result) to avoid recalculating it in future recursive calls.
Main Function:
The Main() function initializes the process by defining the initial state and calling the TopDown() function to solve the problem.

Example: Fibonacci Sequence

Let’s apply the template to a Fibonacci problem as an example:

Memo = {}

Function TopDown(n):
    if n in Memo:
        return Memo[n]

    if n <= 1:
        return n

    Result = TopDown(n-1) + TopDown(n-2)

    Memo[n] = Result
    return Result

Function Main():
    n = 10  // Define the Fibonacci number to calculate
    FinalResult = TopDown(n)
    Print(FinalResult)

Example: Coin Change (Minimum Coins)

Now, let’s apply the template to the Coin Change problem:

Memo = {}

Function CoinChange(coins, amount):
    if amount == 0:
        return 0

    if amount in Memo:
        return Memo[amount]

    Result = INF

    for each coin in coins:
        if amount - coin >= 0:
            SubResult = CoinChange(coins, amount - coin)
            if SubResult != INF:
                Result = Min(Result, SubResult + 1)

    Memo[amount] = Result
    return Result

Function Main():
    coins = [1, 2, 5]
    amount = 11
    FinalResult = CoinChange(coins, amount)

    if FinalResult == INF:
        Print("No solution")
    else:
        Print("Minimum coins:", FinalResult)

1. Minimum (Maximum) Path to Reach a Target

Problem Statement: Given a target, find the minimum (or maximum) cost/path/sum to reach the target.
Top-Down Approach: Recursively compute the minimum (or maximum) cost for each possible path to the target, memoizing intermediate results to avoid redundant calculations.
```
for (int j = 0; j < ways.size(); ++j) {
    result = min(result, topDown(target - ways[j]) + cost/path/sum);
}
return memo[state] = result;
```

2. Distinct Ways

Problem Statement: Given a target, find the number of distinct ways to reach the target.
Top-Down Approach: Recursively calculate the sum of all possible ways to reach the target by using subproblems, and memoize the results.
```
for (int j = 0; j < ways.size(); ++j) {
    result += topDown(target - ways[j]);
}
return memo[state] = result;
```

3. Merging Intervals

Problem Statement: Given a set of intervals or numbers, find an optimal solution considering the current interval and the best you can get from the left and right sides.

Top-Down Approach: Use recursion to consider each interval, calculating the optimal result from the left and right sides and combining them.

for (int k = i; k <= j; ++k) {
    result = max(result, topDown(nums, i, k-1) + result[k] + topDown(nums, k+1, j));
}
return memo[state] = result;

4. DP on Strings

Problem Statement: Given two strings (or a string), return some result (e.g., longest common subsequence, edit distance).

Top-Down Approach: Use two nested loops to compare characters from both strings, solving smaller subproblems recursively and memoizing results to avoid recomputation.

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (s1[i-1] == s2[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

5. Decision Making

Problem Statement: Given a set of values, decide whether to use or ignore the current value based on previous results.
Top-Down Approach: Recursively decide whether to include or exclude the current value based on the optimal solution for subproblems, memoizing the results.
```
for (int i = 1; i < n; ++i) {
    dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
}
```

For each pattern, the general idea in the top-down approach is to define a recursive function that computes the result by breaking down the problem into smaller subproblems, using memoization to store intermediate results. This avoids recomputation and optimizes the solution for large inputs.