Master Dynamic Programming: From Fibonacci to Knapsack, Levenshtein & LCS in Java

1. Introduction

Dynamic programming optimizes recursive algorithms that would otherwise expand exponentially by breaking complex problems into smaller sub‑problems and storing their results in memory to avoid redundant calculations.

What is dynamic programming?

Greedy algorithms

Simplified knapsack problem

Traditional knapsack problem

Longest common subsequence (LCS)

Other DP problems

Conclusion

All code examples are written in java.

2. What is Dynamic Programming?

Dynamic programming solves a problem by dividing it into smaller sub‑problems, similar to recursion, but each distinct sub‑problem is solved only once. The classic example is the Fibonacci sequence, where the recurrence relation is illustrated below.

Computing each Fibonacci number recursively leads to many repeated calculations, as shown in the following diagram.

To avoid this redundancy, dynamic programming stores intermediate results, making each Fibonacci computation O(1) after the first two values are known.

3. Greedy Algorithm Example (Rod Cutting)

Given a rod of length n and an array of prices for each piece length, the goal is to maximize revenue by cutting the rod. The naive recursive solution ( naiveSolution) explores all possibilities and is extremely slow.

public class naiveSolution {
    static int getValue(int[] values, int length) {
        if (length <= 0) return 0;
        int tmpMax = -1;
        for (int i = 0; i < length; i++) {
            tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
        }
        return tmpMax;
    }
    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;
        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

Output:

Max rod value: 17

3.2 Dynamic Programming Solution

The DP version builds a table of sub‑solutions, eliminating repeated recursion.

public class dpSolution {
    static int getValue(int[] values, int rodLength) {
        int[] subSolutions = new int[rodLength + 1];
        for (int i = 1; i <= rodLength; i++) {
            int tmpMax = -1;
            for (int j = 0; j < i; j++)
                tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
            subSolutions[i] = tmpMax;
        }
        return subSolutions[rodLength];
    }
    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;
        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

Output is identical, but the DP version runs in milliseconds instead of seconds.

4. Simplified Knapsack Problem

Given item weights w1, w2, … and a capacity K, determine whether a subset of items fits exactly into the knapsack.

Given a set of items, each with a weight w1, w2... determine the number of each item to put in a knapsack so that the total weight is less than or equal to a given limit K.

4.1 Matrix Initialization

Initialize a matrix M[x][y] where M[x][y].exists indicates if a solution exists for the first x items and capacity y. Base cases:

M[0][k].exists = false for k > 0;
M[0][0].exists = true;

4.2 Algorithm Principles

if (M[i-1][k].exists == True) {
    M[i][k].exists = True;
    M[i][k].includes = False;
} else if (k-W[i] >= 0) {
    if (M[i-1][k-W[i]].exists == true) {
        M[i][k].exists = True;
        M[i][k].includes = True;
    }
} else {
    M[i][k].exists = False;
}

The two cases handle using or not using the current item.

4.3 Implementation

public class Element {
    private boolean exists;
    private boolean includes;
    public Element(boolean exists, boolean includes) {
        this.exists = exists;
        this.includes = includes;
    }
    public Element(boolean exists) {
        this.exists = exists;
        this.includes = false;
    }
    public boolean isExists() { return exists; }
    public void setExists(boolean exists) { this.exists = exists; }
    public boolean isIncludes() { return includes; }
    public void setIncludes(boolean includes) { this.includes = includes; }
}

The main class reads knapsack capacity, number of items, and their weights, then fills the Element[][] elementMatrix according to the DP rules.

public class Knapsack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Insert knapsack capacity:");
        int k = scanner.nextInt();
        System.out.println("Insert number of items:");
        int n = scanner.nextInt();
        System.out.println("Insert weights: ");
        int[] weights = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            weights[i] = scanner.nextInt();
        }
        Element[][] elementMatrix = new Element[n + 1][k + 1];
        elementMatrix[0][0] = new Element(true);
        for (int i = 1; i <= k; i++) {
            elementMatrix[0][i] = new Element(false);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                elementMatrix[i][j] = new Element(false);
                if (elementMatrix[i - 1][j].isExists()) {
                    elementMatrix[i][j].setExists(true);
                    elementMatrix[i][j].setIncludes(false);
                } else if (j >= weights[i]) {
                    if (elementMatrix[i - 1][j - weights[i]].isExists()) {
                        elementMatrix[i][j].setExists(true);
                        elementMatrix[i][j].setIncludes(true);
                    }
                }
            }
        }
        System.out.println(elementMatrix[n][k].isExists());
    }
}

Solution reconstruction traverses the matrix from elementMatrix[n][k] back to the origin, collecting the indices of items that are included.

List<Integer> solution = new ArrayList<>();
if (elementMatrix[n][k].isExists()) {
    int i = n, j = k;
    while (j > 0 && i > 0) {
        if (elementMatrix[i][j].isIncludes()) {
            solution.add(i);
            j = j - weights[i];
        }
        i = i - 1;
    }
}
System.out.println("The elements with the following indexes are in the solution:
" + solution);

5. Traditional Knapsack Problem

The classic version adds a value v_i to each item and seeks the maximum total value without exceeding capacity. The Element class now stores an additional value field.

public class Element {
    private boolean exists;
    private boolean includes;
    private int value;
    // constructors, getters, setters omitted for brevity
}

The DP loop updates both existence and the best value, also tracking how many of each item are used.

if (j >= weights[i]) {
    if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
        if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
            elementMatrix[i][j].setIncludes(true);
            elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
            contains[i][j] = contains[i][j - weights[i]] + 1;
        }
    }
}

Sample output shows the optimal value and the composition of the knapsack.

6. Levenshtein Distance (Edit Distance)

The edit distance between two strings A and B is the minimum number of atomic operations (insert, delete, replace) required to transform A into B. The DP matrix distance[i][j] stores the edit distance for the first i characters of A and the first j characters of B.

public class editDistance {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Insert first string:");
        String s1 = scanner.next();
        System.out.println("Insert second string:");
        String s2 = scanner.next();
        int n = s1.length();
        int m = s2.length();
        int[][] distance = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) distance[i][0] = i;
        for (int j = 0; j <= m; j++) distance[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int e1 = distance[i - 1][j] + 1; // deletion
                int e2 = distance[i][j - 1] + 1; // insertion
                int e3 = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? distance[i - 1][j - 1] : distance[i - 1][j - 1] + 1; // substitution
                distance[i][j] = Math.min(e3, Math.min(e1, e2));
            }
        }
        System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]);
    }
}

Example: transforming "man" to "machine" yields an edit distance of 3.

7. Longest Common Subsequence (LCS)

LCS finds the length of the longest subsequence present in both strings (order preserved, not necessarily contiguous). The DP recurrence is similar to edit distance but without insertion/deletion costs.

public class LCS {
    public static void main(String[] args) {
        String s1 = "Hillfinger";
        String s2 = "Hilfiger";
        int n = s1.length();
        int m = s2.length();
        int[][] solutionMatrix = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) solutionMatrix[i][0] = 0;
        for (int j = 0; j <= m; j++) solutionMatrix[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int max1 = solutionMatrix[i - 1][j];
                int max2 = solutionMatrix[i][j - 1];
                int max3 = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? solutionMatrix[i - 1][j - 1] + 1 : solutionMatrix[i - 1][j - 1];
                solutionMatrix[i][j] = Math.max(max3, Math.max(max1, max2));
            }
        }
        System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
    }
}

Output for the example strings is 8.

8. Other Problems Solved by DP

Partition problem – can a set be split into two subsets with equal sum?

Subset‑sum problem – does a subset sum to a target value?

Coin change – number of ways to make change with unlimited coin denominations.

Counting solutions of a linear equation with k variables.

Probability of a drunkard not falling off a cliff given biased steps.

9. Conclusion

Dynamic programming trades increased memory usage for dramatically reduced computation time. When CPU cycles are precious, a DP solution is preferable; when memory is constrained, a slower recursive approach may be necessary.