Understanding Dynamic Programming

Dynamic programming (DP) is an optimization technique used to solve complex problems by breaking them into simpler subproblems. It stores the results of subproblems to avoid redundant computations, thereby improving efficiency. This article explores fundamental DP concepts and implementations through various algorithmic examples.

1. Fibonacci Sequence

The Fibonacci sequence is a classic example of dynamic programming. The naive recursive solution is highly inefficient due to repeated calculations. A bottom-up DP approach eliminates redundancy by storing intermediate results.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fib(13));
    }

    public static int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

2. Shortest Path - Bellman-Ford Algorithm

The Bellman-Ford algorithm computes the shortest path from a single source in a weighted graph, even if some edges have negative weights. It uses a DP approach to relax all edges repeatedly.

import java.util.*;

public class BellmanFord {
    static class Edge {
        int source, destination, weight;

        public Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        List<edge> edges = Arrays.asList(
            new Edge(1, 2, 7),
            new Edge(1, 3, 9),
            new Edge(1, 6, 14),
            new Edge(2, 4, 15),
            new Edge(3, 4, 11),
            new Edge(3, 6, 2),
            new Edge(4, 5, 6),
            new Edge(5, 6, 9)
        );

        int[] dp = new int[7];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[1] = 0;

        for (int i = 0; i < 5; i++) {
            for (Edge edge : edges) {
                if (dp[edge.source] != Integer.MAX_VALUE / 2 && dp[edge.destination] > dp[edge.source] + edge.weight) {
                    dp[edge.destination] = dp[edge.source] + edge.weight;
                }
            }
        }

        System.out.println(Arrays.toString(dp));
    }
}
</edge>

3. Unique Paths (LeetCode 62)

A robot starts at the top-left corner of an m x n grid and can only move right or down. The task is to find the number of unique paths to the bottom-right corner.

public class UniquePaths {
    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7));
    }

    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

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

4. 0/1 Knapsack Problem

In the 0/1 knapsack problem, each item can be either taken or left. The goal is to maximize value with out exceeding weight capacity.

public class KnapsackProblem {
    static class Item {
        int weight, value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static int solve(Item[] items, int capacity) {
        int[] dp = new int[capacity + 1];

        for (Item item : items) {
            for (int j = capacity; j >= item.weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(4, 1600),
            new Item(8, 2400),
            new Item(5, 30),
            new Item(1, 10000)
        };
        System.out.println(solve(items, 10));
    }
}

5. Coin Change Problem (LeetCode 322)

Given coins of different denominations and a total amount, compute the fewest number of coins needed to make up that amount.

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

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

    public static void main(String[] args) {
        System.out.println(minCoins(new int[]{1, 2, 5}, 11));
    }
}

6. Longest Common Subsequence (LeetCode 1143)

Find the length of the longest subsequence common to two strings.

public class LongestCommonSubsequence {
    public static int findLCS(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];
    }

    public static void main(String[] args) {
        System.out.println(findLCS("abcde", "ace"));
    }
}

7. Longest Increasing Subsequence (LeetCode 300)

Find the length of the longest strictly increasing subsequence.

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
    }
}

8. House Robber (LeetCode 198)

You are a robber planning to rob houses arrangde in a line. Each house has a certain amount of money. Adjacent houses have security systems that will trigger alarms if two adjacent houses are robbed. Maximize the stolen value without triggering the alarm.

public class HouseRobber {
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int prev = nums[0], curr = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int temp = curr;
            curr = Math.max(curr, prev + nums[i]);
            prev = temp;
        }
        return curr;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
    }
}

9. Traveling Salesman Problem (TSP)

Given a list of cities and distances between every pair of cities, find the shortest possible route that visits each city exactly once and returns to the starting point.

public class TravelingSalesmanProblem {
    public static int tsp(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
        dp[1][0] = 0;

        for (int mask = 1; mask < 1 << n; mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0) continue;
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue;
                    dp[mask | (1 << v)][v] = Math.min(dp[mask | (1 << v)][v], dp[mask][u] + graph[u][v]);
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp[(1 << n) - 1][i] + graph[i][0]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 1, 2, 3},
            {1, 0, 6, 4},
            {2, 6, 0, 5},
            {3, 4, 5, 0}
        };
        System.out.println(tsp(graph));
    }
}