DYNAMIC PROGRAMMING

Dynamic programming is a technique for solving complex problems by breaking them down into smaller subproblems, solving each of these subproblems only once, and storing their solutions for later use. This approach can greatly reduce the amount of computation required to solve a problem, making it more efficient.

The key idea behind dynamic programming is that if a problem can be broken down into smaller subproblems, and the solutions to these subproblems can be combined to solve the original problem, then the problem can be solved using a recursive approach, where each subproblem is solved only once and its solution is stored in a table or array for later use.

The process of solving a dynamic programming problem typically involves four steps:

Characterize the structure of an optimal solution: The problem is analyzed to determine the subproblems that must be solved, and the relationships between them.
Define the value of an optimal solution recursively: A recursive formula is developed that expresses the value of an optimal solution in terms of the values of its subproblems.
Compute the value of an optimal solution bottom-up: A table or array is constructed to store the values of subproblems, and the values are filled in from the bottom up, starting with the smallest subproblems.
Construct an optimal solution from computed information: An optimal solution to the original problem is constructed using the values stored in the table or array.

Dynamic programming can be used to solve a wide range of problems, including optimization problems, scheduling problems, sequence alignment problems, and more. Some well-known dynamic programming algorithms include the Knapsack problem, the Longest Common Subsequence problem, and the Fibonacci sequence.

FIBONACCI SEQUENCE

The Fibonacci sequence is a famous sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. We can easily compute each term in the sequence recursively by adding up the two previous terms. For example, to compute the 10th term, we would add the 8th and 9th terms.

However, this recursive approach can be very inefficient, as it will recompute the same terms many times. For example, to compute the 10th term, we would need to compute the 8th term twice, and the 7th term three times. As we compute larger terms in the sequence, this inefficiency becomes even more pronounced.

This is where dynamic programming comes in. The key idea is to use memoization to store the results of intermediate computations, so we don't have to recompute them every time. Specifically, we can use an array to store the computed values of the sequence up to a given index, so we can use them later when computing subsequent terms.

Here's an implementation of the Fibonacci sequence using dynamic programming in Java:


public int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int[] memo = new int[n + 1];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

In this implementation, we first check if the input is 0 or 1, and return the appropriate value. Otherwise, we create an array memo to store the computed values up to n, and initialize the first two values of the array to 0 and 1. We then use a loop to compute the values of the sequence up to n by adding up the previous two values in the array. Finally, we return the value of the nth element in the array.

This implementation has a time complexity of O(n) and a space complexity of O(n), which is much more efficient than the recursive approach. This is the power of dynamic programming: by storing the results of intermediate computations, we can often compute complex functions in polynomial time.

There is a way to compute the nth Fibonacci number without using memoization, which involves keeping only the last two Fibonacci numbers in memory.

Here's an implementation in Java that uses this approach:


public static int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    int a = 0;
    int b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

In this implementation, we initialize a to 0 and b to 1, and then loop through the numbers from 2 to n. At each step, we compute the next Fibonacci number by adding a and b, store it in c, and then update a and b to be the previous two Fibonacci numbers. Finally, we return the value of b, which is the nth Fibonacci number. This implementation is more efficient than the previous memoization-based implementation because it uses constant space (i.e., it only needs to store the last two Fibonacci numbers) and takes linear time (i.e., it needs to compute each Fibonacci number only once).

The approach of building up solutions to a problem by breaking it down into smaller subproblems and reusing solutions to those subproblems, without the use of memoization or recursion, is called "tabulation" or "bottom-up" dynamic programming.

TOP DOWN AND BOTTOM UP

Top-down and bottom-up are two approaches to implementing dynamic programming solutions.

Top-down dynamic programming, also known as memoization, starts with the original problem and breaks it down into smaller subproblems. It then stores the solutions to those subproblems in a cache, or memo, to avoid repeated calculations. When the algorithm encounters a subproblem it has already solved, it simply retrieves the solution from the memo instead of recalculating it. The process continues until the original problem is solved.

Bottom-up dynamic programming, on the other hand, starts with the simplest subproblems and works its way up to the original problem. It solves the subproblems one by one and stores their solutions in a table or array. The algorithm then uses the solutions of the smaller subproblems to solve larger subproblems, until it solves the original problem.

In general, top-down dynamic programming is easier to implement, as it requires less bookkeeping and is often more intuitive. However, bottom-up dynamic programming is usually more efficient in terms of time and space complexity, as it avoids the overhead of recursion and memoization. It also has the advantage of guaranteeing that all subproblems are solved in the correct order, which can be an issue in top-down dynamic programming if the algorithm is not properly implemented.

LONGEST COMMON SUBSEQUENCE

The Longest Common Subsequence (LCS) is a problem in computer science that involves finding the longest subsequence that is common to two given sequences. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For example, consider the two sequences "ABCDGH" and "AEDFHR". The longest common subsequence between them is "ADH" of length 3.

The LCS problem can be solved using dynamic programming. The basic idea is to build a table where each cell represents the length of the LCS between two subsequences. The table is filled in a way that the value in each cell depends on the values of its adjacent cells.

The approach can be done in two ways: top-down and bottom-up.

The top-down approach, also known as memoization, involves breaking the problem into smaller subproblems and storing the results of each subproblem to avoid repeating the same computations. The approach starts with the longest subsequence between the full sequences and recursively builds on top of that.

The bottom-up approach starts with the shortest subsequences and builds up to the longest subsequences using the results of the previously solved subproblems. The approach fills in the table in a systematic way from left to right, and top to bottom.

The time complexity of both approaches is O(mn), where m and n are the lengths of the two input sequences.

Here is an implementation of the Longest Common Subsequence algorithm in Java using dynamic programming (bottom-up approach):


public static int longestCommonSubsequence(String s1, String s2) {
    int n1 = s1.length();
    int n2 = s2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];

    // Fill up the DP table using bottom-up approach
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            // If the last characters match, add one to
        the LCS of the substrings
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
        {
                dp[i][j] = dp[i - 1][j - 1] +
        1;
            } else {
                // If the last characters
        don't match, take the max LCS of the substrings
                dp[i][j] = Math.max(dp[i -
        1][j], dp[i][j - 1]);
            }
        }
    }
    // Return the length of LCS
    return dp[n1][n2];
}

The longestCommonSubsequence method takes two input strings, str1 and str2, and returns the length of their longest common subsequence. It creates a two-dimensional array dp of size (m+1) x (n+1), where m and n are the lengths of str1 and str2, respectively. The array dp[i][j] represents the length of the longest common subsequence of the first i characters of str1 and the first j characters of str2. The base case is when either i or j is 0, in which case dp[i][j] is 0.

The method then uses a nested for loop to fill in the rest of the dp array. If the i-th character of str1 is equal to the j-th character of str2, then the dp[i][j] is equal to dp[i-1][j-1] + 1, since we can add the matching character to the longest common subsequence of the first i-1 characters of str1 and the first j-1 characters of str2. If the characters are not equal, then the dp[i][j] is equal to the maximum of dp[i-1][j] and dp[i][j-1], since we can either skip the i-th character of str1 or the j-th character of str2.

Finally, the method returns dp[m][n], which is the length of the longest common subsequence of str1 and str2. In the example shown, the output is 4, since the longest common subsequence of "AGGTAB" and "GXTXAYB" is "GTAB".

KNAPSACK PROBLEM

The knapsack problem is a classic optimization problem in computer science, which involves finding the optimal selection of items to be included in a knapsack, subject to the knapsack's weight capacity.

In the problem, there are a set of items, each with a weight and a value. The goal is to select a subset of the items such that the total weight is less than or equal to the capacity of the knapsack, and the total value is maximized. The problem can be modeled as an optimization problem in which the objective function is the sum of the values of the selected items, subject to the constraint that the sum of the weights of the selected items is less than or equal to the capacity of the knapsack.

The knapsack problem can be solved using dynamic programming. The idea is to build a table, in which the rows correspond to the items and the columns correspond to the weights. The entry in row i and column j of the table represents the maximum value that can be obtained using items 1 through i, with a weight limit of j. The base case of the table is that the maximum value that can be obtained using no items and a weight limit of 0 is 0.

The dynamic programming algorithm proceeds by filling in the table row by row, using the values in the previous row to compute the values in the current row. For each item i, and each weight j, the maximum value that can be obtained using items 1 through i and a weight limit of j is the maximum of the following two values:

The maximum value that can be obtained using items 1 through i-1 and a weight limit of j (i.e., without including item i).
The value of item i plus the maximum value that can be obtained using items 1 through i-1 and a weight limit of j-wi (i.e., by including item i).

The algorithm returns the maximum value that can be obtained using items 1 through n and a weight limit of W, where n is the number of items and W is the capacity of the knapsack.

Here's an implementation of the 0/1 Knapsack problem in Java:


/**
 * Returns the maximum value that can be put in a knapsack of
        capacity W
 * @param W Capacity of the knapsack
 * @param wt Array of weights of items
 * @param val Array of values of items
 * @param n Number of items
 * @return Maximum value that can be put in a knapsack of capacity
        W
 */
public static int knapSack(int W, int[] wt, int[] val, int n) {

    // Initialize the table to store the maximum value that
        can be achieved for each sub-problem
    int[][] dp = new int[n + 1][W + 1];
    
    // Fill the table in bottom-up manner
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {

            if (i == 0 || w == 0)
        {
                // Base case:
        if either there are no items or the knapsack has no capacity, the maximum value is 0
                dp[i][w] =
        0;
            } else if (wt[i-1] <= w)
        {
                // If the
        weight of the current item is less than or equal to the remaining capacity of the knapsack,
                // we have two
        choices: include the item or exclude it
                dp[i][w] =
        Math.max(val[i-1] + dp[i-1][w-wt[i-1]],  // Include the item
                   
                       dp[i-1][w]);          
                   // Exclude the item
            } else {
                // If the
        weight of the current item is greater than the remaining capacity of the knapsack,
                // we cannot
        include the item
                dp[i][w] =
        dp[i-1][w];  // Exclude the item
            }
        }
    }
    
    return dp[n][W];  // The maximum value that can be
        achieved for the original problem
}

In this implementation, the knapsack function takes in the maximum weight W that the knapsack can hold, the wt array that contains the weights of the items, the val array that contains the values of the items, and the number of items n.

The function first initializes a 2D array K of size (n+1) x (W+1) to store the maximum value that can be obtained with a knapsack of weight w and the first i items.

Then, the function iterates over all possible weights w and all possible items i. If the current item can fit in the knapsack, then the maximum value is either the value of the current item plus the maximum value that can be obtained with the remaining weight and items, or the maximum value that can be obtained without the current item. Otherwise, the maximum value is just the maximum value that can be obtained without the current item.

Finally, the function returns the maximum value that can be obtained with the given maximum weight and items.

MATRIX CHAIN MULTIPLICATION

Matrix Chain Multiplication is a dynamic programming problem that involves finding the optimal way to multiply a series of matrices. Given a sequence of matrices, the goal is to determine the most efficient way to multiply them so as to minimize the number of scalar multiplications required.

For example, consider the sequence of matrices A1, A2, A3, A4, and A5. Suppose that the dimensions of the matrices are as follows:

A1: 10 x 20

A2: 20 x 30

A3: 30 x 40

A4: 40 x 30

A5: 30 x 10

There are many possible ways to multiply these matrices, but some are more efficient than others. For example, one way to multiply them is as follows:

((A1 x A2) x (A3 x A4)) x A5

This involves two matrix multiplications with 20 x 30 x 40, and 10 x 20 x 30 x 40 scalar multiplications, respectively.

Another possible way to multiply them is:

(A1 x (A2 x (A3 x (A4 x A5))))

This involves four matrix multiplications with 20 x 30 x 40, 10 x 20 x 30, 10 x 30 x 10, and 40 x 10 x 10 scalar multiplications, respectively.

The goal of the Matrix Chain Multiplication problem is to find the most efficient way to multiply the matrices in terms of the number of scalar multiplications required.

One approach to solve this problem is to use dynamic programming, where we build up a table of solutions to subproblems and use these solutions to solve larger subproblems. Specifically, we can define an n x n table m where m[i][j] is the minimum number of scalar multiplications required to multiply the matrices from Ai to Aj.

We can fill in this table using a bottom-up approach, starting with subproblems involving only one matrix (m[i][i] = 0) and gradually building up to larger subproblems. For each subproblem of size k (1 <= k <= n), we consider all possible ways to split the matrices from i to j into two groups (i to i+k-1 and i+k to j), and choose the split that results in the minimum number of scalar multiplications.

The time complexity of this algorithm is O(n^3) and the space complexity is O(n^2).

Here's an implementation of the Matrix Chain Multiplication problem using dynamic programming in Java:


public static int matrixChainOrder(int[] p) {
    int n = p.length - 1; // number of matrices
    
    // create a table to store the minimum number of
        multiplications needed to compute the product of i to j matrices
    int[][] m = new int[n][n];
    
    // initialize the table with 0s, since the minimum number
        of multiplications needed to compute a single matrix is 0
    for (int i = 0; i < n; i++) {
        m[i][i] = 0;
    }
    
    // l is the chain length
    for (int l = 2; l <= n; l++) {
        // i is the start of the chain
        for (int i = 0; i < n - l + 1; i++)
        {
            // j is the end of the
        chain
            int j = i + l - 1;
            m[i][j] =
        Integer.MAX_VALUE;
            // k is the split point of
        the chain
            for (int k = i; k < j;
        k++) {
                // compute the
        number of multiplications needed to compute the product of the left and right sub-chains, plus the cost of
        multiplying these two sub-products
                int q = m[i][k]
        + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                // update the
        minimum number of multiplications needed
                if (q <
        m[i][j]) {
                   
        m[i][j] = q;
                }
            }
        }
    }
    
    // return the minimum number of multiplications needed to
        compute the product of all matrices
    return m[0][n-1];
}

This implementation uses a two-dimensional array m to store the minimum number of scalar multiplications required to multiply the matrices. The implementation iterates over all sub-chains of increasing length, calculating the optimal way to multiply each sub-chain. Finally, it returns the minimum cost of multiplying the entire chain. The time complexity of this implementation is O(n^3), where n is the number of matrices in the chain.

EDIT DISTANCE

The edit distance problem, also known as Levenshtein distance, is a way to measure the difference between two strings. It is the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into the other.

For example, the edit distance between the strings "cat" and "bat" is 1, because only one substitution operation (replacing 'c' with 'b') is required to transform "cat" into "bat".

The problem can be solved using dynamic programming. We can define a 2D array dp of size (m+1) x (n+1), where m and n are the lengths of the two strings. The value of dp[i][j] represents the edit distance between the first i characters of the first string and the first j characters of the second string.

The base case is when one of the strings is empty, in which case the edit distance is the length of the other string. We can fill the first row and column of the dp array accordingly. Then, we can fill the rest of the array by considering the three possible operations (insertion, deletion, substitution) and taking the minimum of the resulting values.

The final answer will be stored in dp[m][n].

Here is an example implementation of the edit distance problem in Java:


/**
 * Computes the edit distance between two strings using dynamic
        programming.
 *
 * @param s the first string
 * @param t the second string
 * @return the edit distance between the two strings
 */
public static int computeEditDistance(String s, String t) {
    int n = s.length();
    int m = t.length();

    // Create a table to store the edit distances between all
        pairs of prefixes
    // of the two strings.
    int[][] dp = new int[n + 1][m + 1];

    // Initialize the table with the base cases:
    // the edit distance between the empty string and a
        non-empty string is the
    // length of the non-empty string, and vice versa.

    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }

    // Compute the edit distance between all pairs of
        prefixes of the two strings,
    // using the following recurrence:
    // dp[i][j] = dp[i - 1][j - 1] if s[i] == t[j]
    // dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j
        - 1]) + 1 if s[i] != t[j]
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s.charAt(i - 1) ==
        t.charAt(j - 1)) {
                dp[i][j] = dp[i
        - 1][j - 1];
            } else {
                dp[i][j] =
        Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }

    // The final edit distance is the value in the
        bottom-right corner of the table.
    return dp[n][m];
}

In this implementation, we use three variables to represent the three possible operations:

insert: the edit distance if we insert a character into s1
delete: the edit distance if we delete a character from s1
replace: the edit distance if we replace a character in s1 with a character in s2

We take the minimum of these three values to compute dp[i][j]. The Math.min() function is used to take the minimum value.

PROBLEMS

Easy

Medium

Hard