Matrix Chain Mulitplication

Matrix chain multiplication finds the optimal parenthesization to minimize scalar multiplications. The recurrence relation is:

m[i,j] = 0 if i = j
        min(m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]) for i ≤ k < j if i < j

Three nested loops are required:

• Outer loop: chain length
• Middle loop: starting index
• Inner loop: partition point within the current chain

public class MatrixChainOptimization {
    public static int computeOptimalCost(int[] dimensions) {
        int n = dimensions.length - 1;
        int[][] costTable = new int[n][n];
        
        for (int chainLen = 2; chainLen <= n; chainLen++) {
            for (int start = 0; start <= n - chainLen; start++) {
                int end = start + chainLen - 1;
                costTable[start][end] = Integer.MAX_VALUE;
                
                for (int split = start; split < end; split++) {
                    int currentCost = costTable[start][split] + 
                                    costTable[split + 1][end] + 
                                    dimensions[start] * dimensions[split + 1] * dimensions[end + 1];
                    
                    if (currentCost < costTable[start][end]) {
                        costTable[start][end] = currentCost;
                    }
                }
            }
        }
        return costTable[0][n - 1];
    }
}

Longest Common Subsequence

The longest common subsequence (LCS) problem finds the longest sequence present in both strings. The recurrence is:

lcs[i,j] = 0 if i = 0 or j = 0
          lcs[i-1,j-1] + 1 if chars match
          max(lcs[i-1,j], lcs[i,j-1]) otherwise

public class LongestCommonSubsequence {
    public static int findLCSLength(String str1, String str2) {
        char[] seq1 = str1.toCharArray();
        char[] seq2 = str2.toCharArray();
        int[][] lcsTable = new int[seq1.length + 1][seq2.length + 1];
        
        for (int i = 1; i <= seq1.length; i++) {
            for (int j = 1; j <= seq2.length; j++) {
                if (seq1[i - 1] == seq2[j - 1]) {
                    lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1;
                } else {
                    lcsTable[i][j] = Math.max(lcsTable[i - 1][j], lcsTable[i][j - 1]);
                }
            }
        }
        return lcsTable[seq1.length][seq2.length];
    }
}

Dynamic programming problems require identifying optimal substrutcure and overlapping subproblems. Key variables typically represent problem dimensions or states, and solutions build up from smaller subproblems to the complete solution.