Dynamic Programming » BlackFlow

Introduction

Dynamic Programming (DP) is a powerful algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. It’s particularly effective when a problem has overlapping subproblems and optimal substructure properties.

In this article, we’ll explore Dynamic Programming concepts through practical LeetCode problems, providing clean, well-explained solutions in both C# and Python.

What is Dynamic Programming?

Dynamic Programming is a method for solving complex problems by:

Breaking them into simpler subproblems
Solving each subproblem only once
Storing results to avoid redundant calculations
Building up solutions from smaller subproblems

Key DP Concepts:

1. Overlapping Subproblems The same subproblems are solved multiple times. DP stores results to avoid recomputation.

2. Optimal Substructure An optimal solution contains optimal solutions to subproblems.

3. Memoization (Top-Down) Recursive approach with caching. Start from the problem and work down to base cases.

4. Tabulation (Bottom-Up) Iterative approach. Start from base cases and build up to the solution.

When to Use Dynamic Programming:

Optimization problems (maximize/minimize)
Counting problems (number of ways)
Decision problems (can it be done?)
Problems with overlapping subproblems
Problems with optimal substructure

Problem 1: Longest Increasing Subsequence

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

Example

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Understanding the Problem

For each position i, we need to find the longest increasing subsequence ending at i. We do this by checking all previous positions j < i where nums[j] < nums[i].

Solution Strategy

DP Array Approach:

Initialize dp[i] = 1 for all positions (each element is a subsequence of length 1)
For each position i, look back at all positions j < i
If nums[i] > nums[j], update dp[i] = max(dp[i], dp[j] + 1)
Return the maximum value in the dp array

C# Solution

public class Solution 
{
    public int LengthOfLIS(int[] nums) 
    {
        if (nums.Length == 0)
            return 0;
        
        int size = nums.Length;
        // Initialize dp array: each element is a subsequence of length 1
        int[] dp = Enumerable.Repeat(1, size).ToArray();
        
        for (int i = 1; i < size; i++)
        {
            // Look back at all previous positions
            for (int j = 0; j < i; j++)
            {
                // If current element is greater, extend the subsequence
                if (nums[i] > nums[j])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp.Max();
    }
}

Python 3 Solution

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        size = len(nums)
        dp = [1] * size
        
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j])
        
        return max(dp)

Complexity Analysis

Time Complexity: O(n²) where n is the length of nums
Space Complexity: O(n) for the dp array

Problem 2: Maximum Subarray

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Understanding the Problem

This is Kadane’s Algorithm. At each position, we decide: should we extend the previous subarray or start a new one? We choose whichever gives a larger sum.

Solution Strategy

Kadane’s Algorithm:

Track currentSum: maximum sum ending at current position
Track maxSum: overall maximum sum seen so far
For each element: currentSum = max(nums[i], currentSum + nums[i])
Update maxSum if currentSum is larger

C# Solution

public class Solution 
{
    public int MaxSubArray(int[] nums) 
    {
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.Length; i++)
        {
            // Either extend previous subarray or start new one
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            
            // Update maximum sum seen so far
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Python 3 Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        currentSum = maxSum = nums[0]
        
        for num in nums[1:]:
            currentSum = max(num, currentSum + num)
            maxSum = max(maxSum, currentSum)
        
        return maxSum

Complexity Analysis

Time Complexity: O(n) where n is the length of nums
Space Complexity: O(1) – only using constant extra space

Problem 3: Unique Paths

Problem Statement

There is a robot on an m x n grid. The robot is initially located at the top-left corner (grid[0][0]). The robot tries to move to the bottom-right corner (grid[m – 1][n – 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Understanding the Problem

At each cell, the robot can only come from the cell above (if moving down) or the cell to the left (if moving right). The number of paths to a cell is the sum of paths from top and left cells.

Solution Strategy

DP with Space Optimization:

Initialize a 1D array of size n with all 1s (first row)
For each subsequent row, update: dp[j] = dp[j-1] + dp[j]
dp[j-1] represents paths from left, dp[j] represents paths from top
Return the last element

C# Solution

public class Solution 
{
    public int UniquePaths(int m, int n) 
    {
        // Initialize first row: all cells have 1 path
        int[] dp = Enumerable.Repeat(1, n).ToArray();
        
        // Process each row
        for (int i = 1; i < m; i++)
        {
            // Process each column
            for (int j = 1; j < n; j++)
            {
                // Paths from left + paths from top
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        
        return dp[n - 1];
    }
}

Python 3 Solution

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        
        for i in range(1, m):
            for j in range(1, n):
                dp[j] = dp[j - 1] + dp[j]
        
        return dp[-1]

Complexity Analysis

Time Complexity: O(m × n)
Space Complexity: O(n) – optimized from O(m × n)

Problem 4: Unique Paths II

Problem Statement

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and space is marked as 1 and 0 respectively in the grid.

Understanding the Problem

Similar to Unique Paths, but obstacles block certain cells. If a cell has an obstacle, no paths can go through it.

Solution Strategy

DP with Obstacle Handling:

Initialize dp[0] = 1 (starting position)
For each row, process each column
If cell has obstacle, set dp[i] = 0
Otherwise, dp[i] += dp[i-1] (paths from left)
Return the last element

C# Solution

public class Solution 
{
    public int UniquePathsWithObstacles(int[][] obstacleGrid) 
    {
        int width = obstacleGrid[0].Length;
        int[] dp = new int[width];
        
        // Starting position
        dp[0] = 1;
        
        foreach (int[] row in obstacleGrid)
        {
            for (int i = 0; i < width; i++)
            {
                // If obstacle, no paths through this cell
                if (row[i] == 1)
                {
                    dp[i] = 0;
                }
                // Otherwise, add paths from left
                else if (i > 0)
                {
                    dp[i] += dp[i - 1];
                }
            }
        }
        
        return dp[width - 1];
    }
}

Python 3 Solution

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        width = len(obstacleGrid[0])
        dp = [0] * width
        dp[0] = 1
        
        for row in obstacleGrid:
            for i in range(width):
                if row[i] == 1:
                    dp[i] = 0
                elif i > 0:
                    dp[i] += dp[i - 1]
        
        return dp[-1]

Complexity Analysis

Time Complexity: O(m × n)
Space Complexity: O(n)

Problem 5: House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Understanding the Problem

At each house, we decide: rob it or skip it. If we rob it, we can’t rob the previous house. We want to maximize the total money.

Solution Strategy

State Variables:

previous: Maximum money from houses up to i-2
current: Maximum money from houses up to i-1

For each house: current = max(previous + nums[i], current)

C# Solution

public class Solution 
{
    public int Rob(int[] nums) 
    {
        // previous: maximum gain using houses up to i-2
        // current: maximum gain using houses up to i-1
        int previous = 0, current = 0;
        
        foreach (int num in nums)
        {
            // Either rob current house + previous max, or skip current house
            int temp = Math.Max(previous + num, current);
            
            // Update for next iteration
            previous = current;
            current = temp;
        }
        
        return current;
    }
}

Python 3 Solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        previous, current = 0, 0
        
        for num in nums:
            temp = max(previous + num, current)
            previous = current
            current = temp
        
        return current

Complexity Analysis

Time Complexity: O(n) where n is the number of houses
Space Complexity: O(1) – only using two variables

Problem 6: House Robber II

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Understanding the Problem

Since houses are in a circle, the first and last houses are adjacent. We need to consider two cases:

Rob houses from index 0 to n-2 (exclude last)
Rob houses from index 1 to n-1 (exclude first)

Take the maximum of both cases.

Solution Strategy

Two-Pass Approach:

First pass: Rob houses 0 to n-2 (exclude last house)
Second pass: Rob houses 1 to n-1 (exclude first house)
Return maximum of both cases

C# Solution

public class Solution 
{
    public int Rob(int[] nums) 
    {
        if (nums.Length == 0) 
            return 0;
        
        if (nums.Length == 1) 
            return nums[0];
        
        // Case 1: Rob houses 0 to n-2 (exclude last)
        int previousNotRobbed = 0, currentNotRobbed = 0;
        
        // Case 2: Rob houses 1 to n-1 (exclude first)
        int previousRobbed = 0, currentRobbed = 0;
        
        for (int i = 0; i < nums.Length - 1; i++)
        {
            // Case 1: Exclude last house
            int tempNotRobbed = previousNotRobbed;
            previousNotRobbed = currentNotRobbed;
            currentNotRobbed = Math.Max(tempNotRobbed + nums[i], previousNotRobbed);
            
            // Case 2: Exclude first house (shift by 1)
            int tempRobbed = previousRobbed;
            previousRobbed = currentRobbed;
            currentRobbed = Math.Max(tempRobbed + nums[i + 1], previousRobbed);
        }
        
        return Math.Max(currentRobbed, currentNotRobbed);
    }
}

Python 3 Solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        previousRobbed, currentRobbed = 0, 0
        previousNotRobbed, currentNotRobbed = 0, 0
        
        for i in range(len(nums) - 1):
            tempNotRobbed = previousNotRobbed
            previousNotRobbed = currentNotRobbed
            currentNotRobbed = max(tempNotRobbed + nums[i], previousNotRobbed)
            
            tempRobbed = previousRobbed
            previousRobbed = currentRobbed
            currentRobbed = max(tempRobbed + nums[i + 1], previousRobbed)
        
        return max(currentRobbed, currentNotRobbed)

Complexity Analysis

Time Complexity: O(n) where n is the number of houses
Space Complexity: O(1)

Problem 7: Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Understanding the Problem

We need to find the maximum difference between a later price and an earlier price. Track the minimum price seen so far and the maximum profit.

Solution Strategy

Single Pass:

Track minPrice: minimum price seen so far
Track maxProfit: maximum profit achievable
For each price: update min and calculate profit

C# Solution

public class Solution 
{
    public int MaxProfit(int[] prices) 
    {
        int maxProfit = 0;
        int minPrice = int.MaxValue;
        
        foreach (int price in prices)
        {
            // Update minimum price seen so far
            minPrice = Math.Min(price, minPrice);
            
            // Calculate profit if selling today
            maxProfit = Math.Max(price - minPrice, maxProfit);
        }
        
        return maxProfit;
    }
}

Python 3 Solution

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        minPrice = sys.maxsize
        
        for price in prices:
            minPrice = min(price, minPrice)
            maxProfit = max(price - minPrice, maxProfit)
        
        return maxProfit

Complexity Analysis

Time Complexity: O(n) where n is the length of prices
Space Complexity: O(1)

Problem 8: Best Time to Buy and Sell Stock II

Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Understanding the Problem

We can make multiple transactions. The key insight: we should buy before every price increase and sell before every price decrease. Essentially, we capture every upward price movement.

Solution Strategy

State Machine Approach:

currentHold: Maximum profit while holding a stock
currentNotHold: Maximum profit while not holding a stock

At each day, we can either:

Keep holding or buy (if not holding)
Keep not holding or sell (if holding)

C# Solution

public class Solution 
{
    public int MaxProfit(int[] prices) 
    {
        // Cannot sell on first day, so initialize with negative infinity
        int currentHold = int.MinValue;
        int currentNotHold = 0;
        
        foreach (int price in prices)
        {
            int previousHold = currentHold;
            int previousNotHold = currentNotHold;
            
            // Either keep holding, or buy today
            currentHold = Math.Max(previousHold, previousNotHold - price);
            
            // Either keep not holding, or sell today
            currentNotHold = Math.Max(previousNotHold, previousHold + price);
        }
        
        return prices.Length > 0 ? currentNotHold : 0;
    }
}

Python 3 Solution

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        currentHold, currentNotHold = -sys.maxsize, 0
        
        for price in prices:
            previousHold, previousNotHold = currentHold, currentNotHold
            
            currentHold = max(previousHold, previousNotHold - price)
            currentNotHold = max(previousNotHold, previousHold + price)
        
        return currentNotHold if prices else 0

Complexity Analysis

Time Complexity: O(n) where n is the length of prices
Space Complexity: O(1)

Problem 9: Word Break

Problem Statement

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Understanding the Problem

We need to check if the string can be broken into dictionary words. Use DP: dp[i] represents whether substring s[0..i] can be segmented.

Solution Strategy

DP Array:

dp[0] = true (empty string can be segmented)
For each position i, check all positions j < i
If dp[j] is true and s[j..i] is in dictionary, set dp[i] = true
Return dp[n]

C# Solution

public class Solution 
{
    public bool WordBreak(string s, IList<string> wordDict) 
    {
        int size = s.Length;
        bool[] dp = new bool[size + 1];
        dp[0] = true; // Empty string can be segmented
        
        for (int i = 0; i <= size; i++)
        {
            if (dp[i])
            {
                // Check all substrings starting from position i
                for (int j = i + 1; j <= size; j++)
                {
                    string substring = s.Substring(i, j - i);
                    if (wordDict.Contains(substring))
                    {
                        dp[j] = true;
                    }
                }
            }
        }
        
        return dp[size];
    }
}

Python 3 Solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        size = len(s)
        dp = [False] * (size + 1)
        dp[0] = True
        
        for i in range(size + 1):
            if dp[i]:
                for j in range(i + 1, size + 1):
                    if s[i:j] in wordDict:
                        dp[j] = True
        
        return dp[-1]

Complexity Analysis

Time Complexity: O(n² × m) where n is string length and m is average word length
Space Complexity: O(n) for the dp array

Problem 10: Coin Change

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Understanding the Problem

For each amount from 1 to amount, we find the minimum coins needed. We try each coin and take the minimum.

Solution Strategy

Bottom-Up DP:

Initialize dp[i] = infinity for all amounts (impossible initially)
dp[0] = 0 (0 coins needed for amount 0)
For each amount i, try each coin: dp[i] = min(dp[i], dp[i-coin] + 1)
Return dp[amount] or -1 if still infinity

C# Solution

public class Solution 
{
    public int CoinChange(int[] coins, int amount) 
    {
        int size = amount + 1;
        // Initialize with infinity (impossible)
        float[] dp = Enumerable.Repeat(float.PositiveInfinity, size).ToArray();
        dp[0] = 0; // 0 coins needed for amount 0
        
        for (int i = 1; i < amount + 1; i++)
        {
            foreach (int coin in coins)
            {
                if (i - coin >= 0)
                {
                    // Try using this coin
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        if (dp[amount] == float.PositiveInfinity)
            return -1;
        
        return (int)dp[amount];
    }
}

Python 3 Solution

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        size = amount + 1
        dp = [float('inf')] * size
        dp[0] = 0
        
        for i in range(1, size):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        if dp[-1] == float('inf'):
            return -1
        
        return dp[-1]

Complexity Analysis

Time Complexity: O(amount × coins.length)
Space Complexity: O(amount)

Key Takeaways

Dynamic Programming Patterns:

1. 1D DP Array

Longest Increasing Subsequence
House Robber
Coin Change

2. 2D DP Array (or 1D optimized)

Unique Paths
Grid-based problems

3. State Machine

Best Time to Buy and Sell Stock II
Problems with multiple states

4. String DP

Word Break
Palindrome problems

Common DP Techniques:

Memoization (Top-Down):

Recursive with caching
Natural problem structure
May have stack overflow for deep recursion

Tabulation (Bottom-Up):

Iterative approach
Better space optimization
No recursion overhead

Space Optimization:

Reduce 2D to 1D when possible
Use rolling arrays
Track only necessary previous states

Problem-Solving Steps:

Identify DP pattern: Does it have overlapping subproblems?
Define state: What does dp[i] represent?
Find recurrence relation: How to compute dp[i] from previous states?
Base cases: What are the initial values?
Optimize space: Can we reduce space complexity?

When to Use DP:

Optimization problems (max/min)
Counting problems
Decision problems
Problems asking “how many ways”
Problems with overlapping subproblems
Problems with optimal substructure

Conclusion

Dynamic Programming is a powerful technique for solving optimization and counting problems. The key is recognizing when a problem has overlapping subproblems and optimal substructure, then building a solution from smaller subproblems.

Key patterns to remember:

1D DP: Linear problems, sequences
2D DP: Grid problems, two sequences
State Machine: Problems with multiple states
Bottom-Up: Build from base cases
Top-Down: Break down from problem

Practice identifying DP patterns and building recurrence relations. Start with simpler problems and gradually work up to more complex ones. The more you practice, the better you’ll become at recognizing when and how to apply Dynamic Programming.

Happy coding!