3 - Common Dynamic Programming Problems

Dynamic Programming (DP) is used to solve a wide variety of problems. This section covers some of the most common and classic DP problems, their solutions, and implementations in C#.

Knapsack Problem

The Knapsack Problem is a classic optimization problem where we need to select items to maximize value while staying within a weight constraint.

0/1 Knapsack Problem

In the 0/1 Knapsack Problem, we can either take an item or leave it (we can't take a fraction of an item).

Problem: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value.

Solution

public class Knapsack
{
    public int Solve01Knapsack(int[] weights, int[] values, int capacity)
    {
        int n = weights.Length;
        int[,] dp = new int[n + 1, capacity + 1];
        
        for (int i = 0; i <= n; i++)
        {
            for (int w = 0; w <= capacity; w++)
            {
                if (i == 0 || w == 0)
                    dp[i, w] = 0;
                else if (weights[i - 1] <= w)
                    dp[i, w] = Math.Max(values[i - 1] + dp[i - 1, w - weights[i - 1]], dp[i - 1, w]);
                else
                    dp[i, w] = dp[i - 1, w];
            }
        }
        
        return dp[n, capacity];
    }
    
    // Space-optimized version
    public int Solve01KnapsackOptimized(int[] weights, int[] values, int capacity)
    {
        int n = weights.Length;
        int[] dp = new int[capacity + 1];
        
        for (int i = 0; i < n; i++)
        {
            for (int w = capacity; w >= weights[i]; w--)
            {
                dp[w] = Math.Max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
        
        return dp[capacity];
    }
}

Unbounded Knapsack Problem

In the Unbounded Knapsack Problem, we can take any item multiple times.

Problem: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value. You can use an unlimited number of instances of each item.

Solution

public class Knapsack
{
    public int SolveUnboundedKnapsack(int[] weights, int[] values, int capacity)
    {
        int n = weights.Length;
        int[] dp = new int[capacity + 1];
        
        for (int w = 0; w <= capacity; w++)
        {
            for (int i = 0; i < n; i++)
            {
                if (weights[i] <= w)
                    dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        
        return dp[capacity];
    }
}

Longest Common Subsequence

The Longest Common Subsequence (LCS) problem is to find the longest subsequence common to two sequences.

Problem: Given two strings, find the length of their longest common subsequence.

Solution

public class LCS
{
    public int LongestCommonSubsequence(string text1, string text2)
    {
        int m = text1.Length;
        int n = text2.Length;
        int[,] dp = new int[m + 1, n + 1];
        
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0)
                    dp[i, j] = 0;
                else if (text1[i - 1] == text2[j - 1])
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                else
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
        
        return dp[m, n];
    }
    
    // Space-optimized version
    public int LongestCommonSubsequenceOptimized(string text1, string text2)
    {
        int m = text1.Length;
        int n = text2.Length;
        
        // Make sure text1 is the shorter string
        if (m > n)
        {
            string temp = text1;
            text1 = text2;
            text2 = temp;
            m = text1.Length;
            n = text2.Length;
        }
        
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                    curr[j] = prev[j - 1] + 1;
                else
                    curr[j] = Math.Max(prev[j], curr[j - 1]);
            }
            
            // Swap arrays
            int[] temp = prev;
            prev = curr;
            curr = temp;
            
            // Reset current array
            Array.Clear(curr, 0, curr.Length);
        }
        
        return prev[n];
    }
    
    // Reconstruct the LCS
    public string GetLCS(string text1, string text2)
    {
        int m = text1.Length;
        int n = text2.Length;
        int[,] dp = new int[m + 1, n + 1];
        
        // Fill the dp table
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0)
                    dp[i, j] = 0;
                else if (text1[i - 1] == text2[j - 1])
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                else
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
        
        // Reconstruct the LCS
        int length = dp[m, n];
        char[] lcs = new char[length];
        int index = length - 1;
        
        int i = m, j = n;
        while (i > 0 && j > 0)
        {
            if (text1[i - 1] == text2[j - 1])
            {
                lcs[index] = text1[i - 1];
                i--;
                j--;
                index--;
            }
            else if (dp[i - 1, j] > dp[i, j - 1])
                i--;
            else
                j--;
        }
        
        return new string(lcs);
    }
}

Coin Change Problem

The Coin Change Problem involves finding the minimum number of coins needed to make a specific amount of change.

Problem: Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up that amount.

Solution

public class CoinChange
{
    public int MinCoins(int[] coins, int amount)
    {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, amount + 1); // Initialize with a value larger than any possible solution
        dp[0] = 0; // Base case: 0 coins needed to make 0 amount
        
        for (int i = 1; i <= amount; i++)
        {
            foreach (int coin in coins)
            {
                if (coin <= i)
                {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    // Count the number of ways to make change
    public int CountWays(int[] coins, int amount)
    {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // Base case: 1 way to make 0 amount (by using no coins)
        
        foreach (int coin in coins)
        {
            for (int i = coin; i <= amount; i++)
            {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }
}

Matrix Chain Multiplication

The Matrix Chain Multiplication problem is to find the most efficient way to multiply a given sequence of matrices.

Problem: Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is not to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.

Solution

public class MatrixChainMultiplication
{
    public int MatrixChainOrder(int[] dimensions)
    {
        int n = dimensions.Length - 1; // Number of matrices
        int[,] dp = new int[n, n];
        
        // Cost is zero when multiplying one matrix
        for (int i = 0; i < n; i++)
            dp[i, i] = 0;
        
        // l is chain length
        for (int l = 2; l <= n; l++)
        {
            for (int i = 0; i < n - l + 1; i++)
            {
                int j = i + l - 1;
                dp[i, j] = int.MaxValue;
                
                for (int k = i; k < j; k++)
                {
                    int cost = dp[i, k] + dp[k + 1, j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                    dp[i, j] = Math.Min(dp[i, j], cost);
                }
            }
        }
        
        return dp[0, n - 1];
    }
}

Edit Distance

The Edit Distance problem is to find the minimum number of operations (insert, delete, replace) required to convert one string into another.

Problem: Given two strings, find the minimum number of operations required to convert one string to the other.

Solution

public class EditDistance
{
    public int MinDistance(string word1, string word2)
    {
        int m = word1.Length;
        int n = word2.Length;
        int[,] dp = new int[m + 1, n + 1];
        
        // Base cases: empty strings
        for (int i = 0; i <= m; i++)
            dp[i, 0] = i; // Delete all characters of word1
        
        for (int j = 0; j <= n; j++)
            dp[0, j] = j; // Insert all characters of word2
        
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                    dp[i, j] = dp[i - 1, j - 1]; // No operation needed
                else
                    dp[i, j] = 1 + Math.Min(
                        Math.Min(dp[i - 1, j],    // Delete
                                dp[i, j - 1]),    // Insert
                                dp[i - 1, j - 1]); // Replace
            }
        }
        
        return dp[m, n];
    }
    
    // Space-optimized version
    public int MinDistanceOptimized(string word1, string word2)
    {
        int m = word1.Length;
        int n = word2.Length;
        
        // Make sure word1 is the shorter string
        if (m > n)
        {
            string temp = word1;
            word1 = word2;
            word2 = temp;
            m = word1.Length;
            n = word2.Length;
        }
        
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        // Base case: empty word2
        for (int j = 0; j <= n; j++)
            prev[j] = j;
        
        for (int i = 1; i <= m; i++)
        {
            curr[0] = i; // Base case: empty word1
            
            for (int j = 1; j <= n; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                    curr[j] = prev[j - 1];
                else
                    curr[j] = 1 + Math.Min(
                        Math.Min(prev[j],    // Delete
                                curr[j - 1]),    // Insert
                                prev[j - 1]); // Replace
            }
            
            // Swap arrays
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }
}

Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Problem: Given an array of integers, find the length of the longest strictly increasing subsequence.

Solution

public class LIS
{
    // O(n²) solution
    public int LengthOfLIS(int[] nums)
    {
        if (nums == null || nums.Length == 0)
            return 0;
        
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, 1); // Each element is at least a subsequence of length 1
        
        int maxLength = 1;
        
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.Max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
    
    // O(n log n) solution using binary search
    public int LengthOfLISOptimized(int[] nums)
    {
        if (nums == null || nums.Length == 0)
            return 0;
        
        int n = nums.Length;
        int[] tails = new int[n];
        int size = 0;
        
        foreach (int num in nums)
        {
            int left = 0, right = size;
            
            // Binary search to find the position to insert the current element
            while (left < right)
            {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num)
                    left = mid + 1;
                else
                    right = mid;
            }
            
            tails[left] = num;
            if (left == size)
                size++;
        }
        
        return size;
    }
    
    // Get the actual LIS
    public List<int> GetLIS(int[] nums)
    {
        if (nums == null || nums.Length == 0)
            return new List<int>();
        
        int n = nums.Length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        
        Array.Fill(dp, 1);
        Array.Fill(prev, -1);
        
        int maxLength = 1;
        int endIndex = 0;
        
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            
            if (dp[i] > maxLength)
            {
                maxLength = dp[i];
                endIndex = i;
            }
        }
        
        // Reconstruct the LIS
        List<int> lis = new List<int>();
        while (endIndex != -1)
        {
            lis.Add(nums[endIndex]);
            endIndex = prev[endIndex];
        }
        
        lis.Reverse();
        return lis;
    }
}

Maximum Subarray Sum

The Maximum Subarray Sum problem is to find the contiguous subarray within an array of numbers which has the largest sum.

Problem: Given an array of integers, find the contiguous subarray with the largest sum.

Solution

public class MaximumSubarraySum
{
    // Kadane's Algorithm
    public int MaxSubArray(int[] nums)
    {
        if (nums == null || nums.Length == 0)
            return 0;
        
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        
        for (int i = 1; i < nums.Length; i++)
        {
            maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.Max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }
    
    // Get the actual subarray
    public (int, int, int) MaxSubArrayWithIndices(int[] nums)
    {
        if (nums == null || nums.Length == 0)
            return (0, -1, -1);
        
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        int start = 0;
        int end = 0;
        int s = 0;
        
        for (int i = 1; i < nums.Length; i++)
        {
            if (nums[i] > maxEndingHere + nums[i])
            {
                maxEndingHere = nums[i];
                s = i;
            }
            else
            {
                maxEndingHere = maxEndingHere + nums[i];
            }
            
            if (maxEndingHere > maxSoFar)
            {
                maxSoFar = maxEndingHere;
                start = s;
                end = i;
            }
        }
        
        return (maxSoFar, start, end);
    }
}

Palindromic Substrings

The Palindromic Substrings problem is to count all palindromic substrings of a given string.

Problem: Given a string, count the number of palindromic substrings in it.

Solution

public class PalindromicSubstrings
{
    public int CountSubstrings(string s)
    {
        if (string.IsNullOrEmpty(s))
            return 0;
        
        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int count = 0;
        
        // All substrings of length 1 are palindromes
        for (int i = 0; i < n; i++)
        {
            dp[i, i] = true;
            count++;
        }
        
        // Check for substrings of length 2
        for (int i = 0; i < n - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                dp[i, i + 1] = true;
                count++;
            }
        }
        
        // Check for substrings of length 3 or more
        for (int len = 3; len <= n; len++)
        {
            for (int i = 0; i <= n - len; i++)
            {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i + 1, j - 1])
                {
                    dp[i, j] = true;
                    count++;
                }
            }
        }
        
        return count;
    }
    
    // Expand around center approach (more efficient)
    public int CountSubstringsOptimized(string s)
    {
        if (string.IsNullOrEmpty(s))
            return 0;
        
        int count = 0;
        
        for (int i = 0; i < s.Length; i++)
        {
            // Odd length palindromes with center at i
            count += ExpandAroundCenter(s, i, i);
            
            // Even length palindromes with center between i and i+1
            count += ExpandAroundCenter(s, i, i + 1);
        }
        
        return count;
    }
    
    private int ExpandAroundCenter(string s, int left, int right)
    {
        int count = 0;
        
        while (left >= 0 && right < s.Length && s[left] == s[right])
        {
            count++;
            left--;
            right++;
        }
        
        return count;
    }
}

Conclusion

These common Dynamic Programming problems demonstrate the versatility and power of the DP approach. By breaking down complex problems into simpler subproblems and avoiding redundant calculations, DP provides efficient solutions to a wide range of optimization and counting problems.

When approaching a new problem, try to identify if it has the characteristics of a DP problem (overlapping subproblems and optimal substructure), and then apply the techniques demonstrated in these examples to develop an efficient solution.