Coding Patterns
Dynamic Programming
Code Templates

Code Templates

Master dynamic programming with these optimized code templates. Use them as starting points for solving DP problems across different programming languages and patterns.

Pro Tip: Start with the Concept Guide to understand the theory behind these templates, then practice with our curated problems.

1D Array DP Templates

The Main Template: Fibonacci Numbers

Description: This template demonstrates the core DP pattern for linear sequences. It’s the foundation for problems like Climbing Stairs, House Robber, and Jump Game.

/**
 * Find number of ways to climb n stairs (1 or 2 steps)
 * @param {number} n - Number of stairs
 * @returns {number} Number of ways
 */
function climbStairs(n) {
    if (n <= 1) return 1;

    // Space optimized Fibonacci
    let prev2 = 1, prev1 = 1;

    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}
def climb_stairs(n):
    """
    Find number of ways to climb n stairs (1 or 2 steps)
    """
    if n <= 1:
        return 1

    # Space optimized Fibonacci
    prev2, prev1 = 1, 1

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1
public class Solution {
    /**
     * Find number of ways to climb n stairs (1 or 2 steps)
     */
    public int climbStairs(int n) {
        if (n <= 1) return 1;

        // Space optimized Fibonacci
        int prev2 = 1, prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}
class Solution {
public:
    /**
     * Find number of ways to climb n stairs (1 or 2 steps)
     */
    int climbStairs(int n) {
        if (n <= 1) return 1;

        // Space optimized Fibonacci
        int prev2 = 1, prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};
func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }

    // Space optimized Fibonacci
    prev2, prev1 := 1, 1

    for i := 2; i <= n; i++ {
        current := prev1 + prev2
        prev2, prev1 = prev1, current
    }

    return prev1
}
def climb_stairs(n)
    return 1 if n <= 1

    # Space optimized Fibonacci
    prev2, prev1 = 1, 1

    (2..n).each do |i|
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    end

    prev1
end

Code Breakdown

This template demonstrates the core DP pattern:

Key Variables:

  • prev2: Stores result for i-2
  • prev1: Stores result for i-1
  • current: Stores result for current position i

Visual State Transition:

  stateDiagram-v2
    [*] --> Base: n <= 1
    Base --> Loop: n > 1
    Loop --> Compute: Calculate current
    Compute --> Update: Update prev2, prev1
    Update --> Loop: Continue loop
    Loop --> [*]: i > n

Critical Sections:

  1. Initialization: Handle base cases (n ≤ 1)
  2. Loop: Iterate through all positions
  3. Transition: Apply recurrence relation
  4. Update: Shift variables for next iteration

House Robber Pattern

Description: Maximum money from robbing houses without robbing adjacent houses. This template is directly used in House Robber.

/**
 * Maximum money from robbing houses without robbing adjacent houses
 * @param {number[]} nums - House values
 * @returns {number} Maximum money
 */
function rob(nums) {
    if (!nums.length) return 0;

    // Space optimized: only track two previous states
    let prev2 = 0, prev1 = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}
def rob(nums):
    """
    Maximum money from robbing houses without robbing adjacent houses
    """
    if not nums:
        return 0

    # Space optimized: only track two previous states
    prev2, prev1 = 0, nums[0]

    for i in range(1, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1
public class Solution {
    /**
     * Maximum money from robbing houses without robbing adjacent houses
     */
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;

        // Space optimized: only track two previous states
        int prev2 = 0, prev1 = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}
class Solution {
public:
    /**
     * Maximum money from robbing houses without robbing adjacent houses
     */
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;

        // Space optimized: only track two previous states
        int prev2 = 0, prev1 = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};
func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // Space optimized: only track two previous states
    prev2, prev1 := 0, nums[0]

    for i := 1; i < len(nums); i++ {
        current := max(prev1, prev2+nums[i])
        prev2, prev1 = prev1, current
    }

    return prev1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
def rob(nums)
    return 0 if nums.empty?

    # Space optimized: only track two previous states
    prev2, prev1 = 0, nums[0]

    (1...nums.length).each do |i|
        current = [prev1, prev2 + nums[i]].max
        prev2, prev1 = prev1, current
    end

    prev1
end

2D Matrix DP Templates

Longest Common Subsequence

Description: Find length of longest common subsequence between two strings.

/**
 * Find length of longest common subsequence
 * @param {string} text1 - First string
 * @param {string} text2 - Second string
 * @returns {number} LCS length
 */
function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            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];
}
def longest_common_subsequence(text1, text2):
    """
    Find length of longest common subsequence
    """
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]
public class Solution {
    /**
     * Find length of longest common subsequence
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(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];
    }
}
class Solution {
public:
    /**
     * Find length of longest common subsequence
     */
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

        return dp[m][n];
    }
};
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
def longest_common_subsequence(text1, text2)
    m, n = text1.length, text2.length
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    (1..m).each do |i|
        (1..n).each do |j|
            if text1[i - 1] == text2[j - 1]
                dp[i][j] = dp[i - 1][j - 1] + 1
            else
                dp[i][j] = [dp[i - 1][j], dp[i][j - 1]].max
            end
        end
    end

    dp[m][n]
end

Edit Distance (Levenshtein Distance)

Description: Minimum operations to convert word1 to word2 (insert, delete, replace).

/**
 * Minimum operations to convert word1 to word2 (insert, delete, replace)
 * @param {string} word1 - Source word
 * @param {string} word2 - Target word
 * @returns {number} Minimum operations
 */
function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // Initialize base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,     // Delete
                    dp[i][j - 1] + 1,     // Insert
                    dp[i - 1][j - 1] + 1  // Replace
                );
            }
        }
    }

    return dp[m][n];
}
def min_distance(word1, word2):
    """
    Minimum operations to convert word1 to word2 (insert, delete, replace)
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,     # Delete
                    dp[i][j - 1] + 1,     # Insert
                    dp[i - 1][j - 1] + 1  # Replace
                )

    return dp[m][n]
public class Solution {
    /**
     * Minimum operations to convert word1 to word2 (insert, delete, replace)
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i - 1][j] + 1,     // Delete
                                dp[i][j - 1] + 1),    // Insert
                        dp[i - 1][j - 1] + 1          // Replace
                    );
                }
            }
        }

        return dp[m][n];
    }
}
class Solution {
public:
    /**
     * Minimum operations to convert word1 to word2 (insert, delete, replace)
     */
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        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];
                } else {
                    dp[i][j] = min({
                        dp[i - 1][j] + 1,     // Delete
                        dp[i][j - 1] + 1,     // Insert
                        dp[i - 1][j - 1] + 1  // Replace
                    });
                }
            }
        }

        return dp[m][n];
    }
};
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Initialize base cases
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(
                    min(dp[i-1][j]+1,     // Delete
                        dp[i][j-1]+1),    // Insert
                    dp[i-1][j-1]+1)       // Replace
            }
        }
    }

    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
def min_distance(word1, word2)
    m, n = word1.length, word2.length
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    # Initialize base cases
    (0..m).each { |i| dp[i][0] = i }
    (0..n).each { |j| dp[0][j] = j }

    (1..m).each do |i|
        (1..n).each do |j|
            if word1[i - 1] == word2[j - 1]
                dp[i][j] = dp[i - 1][j - 1]
            else
                dp[i][j] = [
                    dp[i - 1][j] + 1,     # Delete
                    dp[i][j - 1] + 1,     # Insert
                    dp[i - 1][j - 1] + 1  # Replace
                ].min
            end
        end
    end

    dp[m][n]
end

Knapsack DP Templates

0/1 Knapsack

Description: Each item can be used at most once.

/**
 * 0/1 Knapsack: each item can be used at most once
 * @param {number[]} weights - Item weights
 * @param {number[]} values - Item values
 * @param {number} capacity - Knapsack capacity
 * @returns {number} Maximum value
 */
function knapsack01(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i - 1][w],  // Don't take
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]  // Take
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}
def knapsack_01(weights, values, capacity):
    """
    0/1 Knapsack: each item can be used at most once
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],  # Don't take
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]  # Take
                )
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]
public class Solution {
    /**
     * 0/1 Knapsack: each item can be used at most once
     */
    public int knapsack01(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],  // Don't take
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]  // Take
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }
}
class Solution {
public:
    /**
     * 0/1 Knapsack: each item can be used at most once
     */
    int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
        int n = weights.size();
        vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = max(
                        dp[i - 1][w],  // Don't take
                        values[i - 1] + dp[i - 1][w - weights[i - 1]]  // Take
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][capacity];
    }
};
func knapsack01(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= capacity; w++ {
            if weights[i-1] <= w {
                dp[i][w] = max(
                    dp[i-1][w],  // Don't take
                    values[i-1] + dp[i-1][w-weights[i-1]]  // Take
                )
            } else {
                dp[i][w] = dp[i-1][w]
            }
        }
    }

    return dp[n][capacity]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
def knapsack_01(weights, values, capacity)
    n = weights.length
    dp = Array.new(n + 1) { Array.new(capacity + 1, 0) }

    (1..n).each do |i|
        (0..capacity).each do |w|
            if weights[i - 1] <= w
                dp[i][w] = [
                    dp[i - 1][w],  # Don't take
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]  # Take
                ].max
            else
                dp[i][w] = dp[i - 1][w]
            end
        end
    end

    dp[n][capacity]
end

Unbounded Knapsack (Coin Change)

Description: Each item can be used unlimited times.

/**
 * Unbounded Knapsack: each item can be used unlimited times
 * @param {number[]} coins - Available coin denominations
 * @param {number} amount - Target amount
 * @returns {number} Fewest coins needed, or -1 if impossible
 */
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] === amount + 1 ? -1 : dp[amount];
}
def coin_change(coins, amount):
    """
    Unbounded Knapsack: each item can be used unlimited times
    """
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return -1 if dp[amount] == amount + 1 else dp[amount]
public class Solution {
    /**
     * Unbounded Knapsack: each item can be used unlimited times
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}
class Solution {
public:
    /**
     * Unbounded Knapsack: each item can be used unlimited times
     */
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] = min(dp[i], dp[i-coin]+1)
        }
    }

    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
def coin_change(coins, amount)
    dp = Array.new(amount + 1, amount + 1)
    dp[0] = 0

    coins.each do |coin|
        (coin..amount).each do |i|
            dp[i] = [dp[i], dp[i - coin] + 1].min
        end
    end

    dp[amount] == amount + 1 ? -1 : dp[amount]
end

Practice Tips

Choosing Between Approaches

  • Memoization: Natural recursive structure, solves subproblems on demand
  • Tabulation: Space efficient, processes in logical order
  • Space Optimization: Reduce O(n²) to O(n) or O(k) when possible

Common Patterns

  • 1D Array: Linear sequences (house robber, climb stairs)
  • 2D Matrix: String comparisons, LCS, edit distance
  • Knapsack: Optimization with constraints
  • Interval DP: Matrix chain multiplication, palindrome partitioning

Debugging Templates 

// Print DP table
function printDP(dp) {
    for (const row of dp) {
        console.log(row.join(' '));
    }
}

// Verify DP transitions
function verifyDP(i, j, expected, dp) {
    const actual = dp[i][j];
    console.log(`DP[${i}][${j}]: expected ${expected}, got ${actual}`);
}
Language Notes: JavaScript arrays are dynamic but Map provides better performance for memoization. Consider using TypedArray for large DP tables for better memory usage.