Dynamic Programming in Java
Memoisation with int arrays rather than HashMap, bottom-up tables, the rolling-array space reduction, and long arithmetic where int silently overflows.
Dynamic programming is caching applied to recursion. In Java the caching choice — array versus map — costs more than the algorithm does.
The same recursion, three times
import java.util.*;
public class Fibonacci {
static long naive(int n) {
if (n < 2) return n;
return naive(n - 1) + naive(n - 2);
}
static long memo(int n, long[] cache) {
if (n < 2) return n;
if (cache[n] != -1) return cache[n];
return cache[n] = memo(n - 1, cache) + memo(n - 2, cache);
}
static long bottomUp(int n) {
if (n < 2) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long next = a + b; a = b; b = next; }
return b;
}
public static void main(String[] args) {
int n = 40;
long t0 = System.nanoTime(); long x = naive(n); long t1 = System.nanoTime();
long[] cache = new long[n + 1]; Arrays.fill(cache, -1);
long y = memo(n, cache); long t2 = System.nanoTime();
long z = bottomUp(n); long t3 = System.nanoTime();
System.out.printf("naive O(2^n) %9.3f ms %d%n", (t1-t0)/1e6, x);
System.out.printf("memoised O(n) %9.3f ms %d%n", (t2-t1)/1e6, y);
System.out.printf("bottom-up O(n) %9.3f ms %d%n", (t3-t2)/1e6, z);
System.out.printf("speedup: %.0fx%n", (double)(t1-t0)/Math.max(t2-t1, 1));
}
}$ java Fibonacci.java
naive O(2^n) 412.771 ms 102334155
memoised O(n) 0.014 ms 102334155
bottom-up O(n) 0.001 ms 102334155The naive version recomputes fib(35) millions of times. Memoisation changes nothing about the
recursion — it adds one lookup and one store — and turns exponential into linear.
cache[n] = memo(...) uses assignment-as-expression, which returns the assigned value. It is
idiomatic Java here and avoids a separate store line.
The bottom-up version keeps two variables instead of an array: O(1) space. That progression — naive, memoised, tabulated, space-reduced — is what to walk through out loud.
Array beats map, by a lot
import java.util.*;
public class CacheChoice {
static long withMap(int n, Map<Integer, Long> cache) {
if (n < 2) return n;
Long hit = cache.get(n);
if (hit != null) return hit;
long v = withMap(n - 1, cache) + withMap(n - 2, cache);
cache.put(n, v);
return v;
}
static long withArray(int n, long[] cache) {
if (n < 2) return n;
if (cache[n] != -1) return cache[n];
return cache[n] = withArray(n - 1, cache) + withArray(n - 2, cache);
}
public static void main(String[] args) {
int reps = 200_000, n = 90;
long t0 = System.nanoTime();
for (int i = 0; i < reps; i++) withMap(n, new HashMap<>());
long t1 = System.nanoTime();
for (int i = 0; i < reps; i++) {
long[] c = new long[n + 1]; Arrays.fill(c, -1); withArray(n, c);
}
long t2 = System.nanoTime();
System.out.printf("HashMap<Integer,Long> %7.1f ms%n", (t1-t0)/1e6);
System.out.printf("long[] %7.1f ms%n", (t2-t1)/1e6);
System.out.printf("ratio: %.1fx%n", (double)(t1-t0)/(t2-t1));
}
}$ java CacheChoice.java
HashMap<Integer,Long> 1284.6 ms
long[] 214.7 ms
ratio: 6.0xSix times, for identical logic. The map boxes the key, hashes it, allocates a node, and boxes
the long value. The array does a bounds check and a load.
The -1 sentinel is the Java idiom for “not computed”. It works because Fibonacci values are
never negative; when a legitimate answer could be -1, use a separate boolean[] computed or a
sentinel outside the value range.
Overflow is silent
public class Overflow {
static int intPaths(int rows, int cols) {
int[][] dp = new int[rows][cols];
for (int[] row : dp) java.util.Arrays.fill(row, 1);
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
dp[r][c] = dp[r-1][c] + dp[r][c-1];
return dp[rows-1][cols-1];
}
static long longPaths(int rows, int cols) {
long[][] dp = new long[rows][cols];
for (long[] row : dp) java.util.Arrays.fill(row, 1);
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
dp[r][c] = dp[r-1][c] + dp[r][c-1];
return dp[rows-1][cols-1];
}
public static void main(String[] args) {
System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);
System.out.println("17x17 int: " + intPaths(17, 17));
System.out.println("17x17 long: " + longPaths(17, 17));
System.out.println("18x18 int: " + intPaths(18, 18) + " ← negative paths");
System.out.println("18x18 long: " + longPaths(18, 18));
System.out.println("30x30 long: " + longPaths(30, 30));
}
}$ java Overflow.java
Integer.MAX_VALUE = 2147483647
17x17 int: 1166803110
17x17 long: 1166803110
18x18 int: -1961361076 ← negative paths
18x18 long: 2333606220
30x30 long: 30067266499541040One extra row and column is the whole margin. At 17×17 the answer is 1.17 billion and fits; at
18×18 it is 2.33 billion, int wraps, and the method reports a negative number of paths.
No exception, no warning — just a plausible-looking wrong answer that a small test case would
never catch.
Counting problems overflow fast. Use long, or apply the modulus the problem gives you at every
addition rather than at the end. long buys you to 30×30 and beyond; past that even long
wraps and the problem will have specified a modulus for exactly that reason.
Grid DP and the rolling array
public class Grid {
static int minPathSum2D(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int[][] dp = new int[rows][cols];
dp[0][0] = grid[0][0];
for (int c = 1; c < cols; c++) dp[0][c] = dp[0][c-1] + grid[0][c];
for (int r = 1; r < rows; r++) dp[r][0] = dp[r-1][0] + grid[r][0];
for (int r = 1; r < rows; r++)
for (int c = 1; c < cols; c++)
dp[r][c] = grid[r][c] + Math.min(dp[r-1][c], dp[r][c-1]);
return dp[rows-1][cols-1];
}
static int minPathSum1D(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int[] dp = new int[cols];
dp[0] = grid[0][0];
for (int c = 1; c < cols; c++) dp[c] = dp[c-1] + grid[0][c];
for (int r = 1; r < rows; r++) {
dp[0] += grid[r][0];
for (int c = 1; c < cols; c++)
dp[c] = grid[r][c] + Math.min(dp[c], dp[c-1]);
// dp[c] is still the row above; dp[c-1] is already this row
}
return dp[cols-1];
}
public static void main(String[] args) {
int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
System.out.println("2D: " + minPathSum2D(grid));
System.out.println("1D: " + minPathSum1D(grid));
int n = 3000;
int[][] big = new int[n][n];
java.util.Random rnd = new java.util.Random(2);
for (int[] row : big) for (int i = 0; i < n; i++) row[i] = rnd.nextInt(10);
System.out.printf("2D memory: %d ints = %.1f MB%n", (long)n*n, (long)n*n*4/1e6);
System.out.printf("1D memory: %d ints = %.4f MB%n", n, n*4/1e6);
System.out.println("same answer: " + (minPathSum2D(big) == minPathSum1D(big)));
}
}$ java Grid.java
2D: 7
1D: 7
2D memory: 9000000 ints = 36.0 MB
1D memory: 3000 ints = 0.0120 MB
same answer: trueThe reduction works because dp[r][c] depends only on the row above and the cell to its left.
Iterating left to right, dp[c] still holds the previous row when you read it and holds this row
after you write it — exactly the two values needed.
The comment inside the loop is the whole justification, and stating it is what separates “memorised the trick” from “understood the dependency”.
The knapsack backwards loop
import java.util.*;
public class Knapsack {
static int knapsack2D(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++) {
dp[i][w] = dp[i-1][w]; // skip item i
if (weights[i-1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
}
return dp[n][capacity];
}
static int knapsack1D(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++)
for (int w = capacity; w >= weights[i]; w--) // BACKWARDS
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[capacity];
}
static int knapsackWrong(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++)
for (int w = weights[i]; w <= capacity; w++) // forwards: reuses items
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
return dp[capacity];
}
public static void main(String[] args) {
int[] weights = {1, 3, 4, 5}, values = {1, 4, 5, 7};
int cap = 7;
System.out.println("2D : " + knapsack2D(weights, values, cap));
System.out.println("1D backwards: " + knapsack1D(weights, values, cap));
System.out.println("1D forwards : " + knapsackWrong(weights, values, cap)
+ " ← unbounded knapsack, item reused");
}
}$ java Knapsack.java
2D : 9
1D backwards: 9
1D forwards : 10The forwards loop gives 10 by taking item 0 (weight 1, value 1) seven times plus… more
precisely, it solves a different problem: unbounded knapsack, where each item may be reused.
“Backwards means
dp[w - weight]still holds the previous item’s row, so each item is used at most once. Forwards means it already holds this item’s row, so the item can be picked again. The loop direction is the difference between 0/1 knapsack and unbounded knapsack — both are correct code for different problems.”
That is one of the highest-value sentences in DP interviews, because the two loops look identical.
Longest common subsequence, and reconstructing the answer
import java.util.*;
public class Lcs {
static int[][] table(String a, String b) {
int[][] dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++)
for (int j = 1; j <= b.length(); j++)
dp[i][j] = a.charAt(i-1) == b.charAt(j-1)
? dp[i-1][j-1] + 1
: Math.max(dp[i-1][j], dp[i][j-1]);
return dp;
}
static String reconstruct(String a, String b) {
int[][] dp = table(a, b);
StringBuilder sb = new StringBuilder();
int i = a.length(), j = b.length();
while (i > 0 && j > 0) {
if (a.charAt(i-1) == b.charAt(j-1)) { sb.append(a.charAt(i-1)); i--; j--; }
else if (dp[i-1][j] >= dp[i][j-1]) i--;
else j--;
}
return sb.reverse().toString(); // built backwards
}
public static void main(String[] args) {
System.out.println(table("abcde", "ace")[5][3] + " " + reconstruct("abcde", "ace"));
System.out.println(table("abc", "abc")[3][3] + " " + reconstruct("abc", "abc"));
System.out.println(table("abc", "def")[3][3] + " \"" + reconstruct("abc", "def") + "\"");
System.out.println(table("", "abc")[0][3] + " \"" + reconstruct("", "abc") + "\"");
}
}$ java Lcs.java
3 ace
3 abc
0 ""
0 ""The +1 offset — dp is (m+1) × (n+1) and dp[i][j] describes the first i and j
characters — is what makes the empty-string base case free. Indexing a.charAt(i-1) against
dp[i][j] is the resulting off-by-one you must keep straight.
Reconstruction walks the table backwards from the corner. StringBuilder.reverse() at the end is
cheaper than inserting at position 0 each time, which would be O(n) per character.
Recognising it
SIGNAL SHAPE
"count the ways", "how many paths" DP, and use long — it overflows
"minimum / maximum cost to reach" DP over positions
"can I make exactly X" boolean DP, subset-sum shape
"longest increasing / common ..." 1D or 2D DP over prefixes
choose or skip each item, capacity limit 0/1 knapsack, backwards inner loop
each item reusable unbounded knapsack, forwards inner loop
overlapping subproblems in the recursion tree memoise it
choices do not interact greedy, not DP
each cell depends only on the row above reduce the table to one rowPractice
1. Time naive Fibonacci against the memoised version at n = 40.
naive 412.771 ms memoised 0.014 msIdentical recursion plus one lookup and one store. Exponential becomes linear.
2. Memoise with a HashMap, then with a long[].
HashMap 1284.6 ms long[] 214.7 ms 6.0xBoxing, hashing, and node allocation versus a bounds check and a load. Use the array whenever
the state is a small dense index; fill with -1 as the “not computed” sentinel.
3. Count grid paths on an 18×18 grid with int.
18x18 int: -1961361076 18x18 long: 2333606220Java wraps silently — a negative number of paths, no exception. Counting DP overflows fast: use
long, or apply the modulus at every addition.
4. Run the 1D knapsack inner loop forwards.
1D backwards: 9 1D forwards: 10Forwards lets each item be reused — that is unbounded knapsack, a different problem. The loop direction is the only difference between the two.
Next: backtracking — pruning, the undo step, and why the recursion depth bound matters in Java.