Stop memorizing DP solutions. Learn these 5 patterns and you'll recognize DP problems on sight — with Java implementations for each.
Dynamic programming has a reputation for being hard. It isn't — it's just badly taught. There are roughly 5 patterns that cover the vast majority of DP problems. Learn the patterns, not the solutions.
1// dp[i] = max money robbing up to house i
2// Either skip house i (dp[i-1]) or rob it (dp[i-2] + nums[i])
3public int rob(int[] nums) {
4 if (nums.length == 1) return nums[0];
5 int prev2 = nums[0];
6 int prev1 = Math.max(nums[0], nums[1]);
7 for (int i = 2; i < nums.length; i++) {
8 int curr = Math.max(prev1, prev2 + nums[i]);
9 prev2 = prev1;
10 prev1 = curr;
11 }
12 return prev1;
13}1public int uniquePaths(int m, int n) {
2 int[] dp = new int[n];
3 Arrays.fill(dp, 1); // base: top row is all 1s
4 for (int i = 1; i < m; i++) {
5 for (int j = 1; j < n; j++) {
6 dp[j] += dp[j - 1]; // dp[j] = from above, dp[j-1] = from left
7 }
8 }
9 return dp[n - 1];
10}Problems about merging, bursting, or splitting intervals. State = dp[i][j] = optimal answer for subarray [i..j]. Solve smaller intervals first, build up to the full range.
1// 0/1 Knapsack: each item used at most once
2public int knapsack(int[] weights, int[] values, int capacity) {
3 int[] dp = new int[capacity + 1];
4 for (int i = 0; i < weights.length; i++) {
5 // Traverse RIGHT to LEFT to prevent using item twice
6 for (int w = capacity; w >= weights[i]; w--) {
7 dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
8 }
9 }
10 return dp[capacity];
11}
12
13// Unbounded Knapsack (Coin Change): each item used unlimited times
14// Traverse LEFT to RIGHT — allows reuse1public int minDistance(String word1, String word2) {
2 int m = word1.length(), n = word2.length();
3 int[][] dp = new int[m + 1][n + 1];
4 for (int i = 0; i <= m; i++) dp[i][0] = i;
5 for (int j = 0; j <= n; j++) dp[0][j] = j;
6
7 for (int i = 1; i <= m; i++)
8 for (int j = 1; j <= n; j++)
9 if (word1.charAt(i-1) == word2.charAt(j-1))
10 dp[i][j] = dp[i-1][j-1];
11 else
12 dp[i][j] = 1 + Math.min(dp[i-1][j-1],
13 Math.min(dp[i-1][j], dp[i][j-1]));
14 return dp[m][n];
15}When optimizing DP space: if dp[i] only depends on dp[i-1], you can use two 1D arrays instead of a 2D table. If it only depends on dp[i-1][j] and dp[i][j-1], a single 1D array with in-place updates works.
1// Minimum coins to make amount — classic unbounded knapsack
2public int coinChange(int[] coins, int amount) {
3 int[] dp = new int[amount + 1];
4 Arrays.fill(dp, amount + 1); // sentinel: impossible value
5 dp[0] = 0;
6
7 for (int i = 1; i <= amount; i++) {
8 for (int coin : coins) {
9 if (coin <= i) {
10 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
11 }
12 }
13 }
14 return dp[amount] > amount ? -1 : dp[amount];
15}1// O(n²) DP
2public int lengthOfLIS(int[] nums) {
3 int[] dp = new int[nums.length];
4 Arrays.fill(dp, 1);
5 int max = 1;
6 for (int i = 1; i < nums.length; i++) {
7 for (int j = 0; j < i; j++) {
8 if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
9 }
10 max = Math.max(max, dp[i]);
11 }
12 return max;
13}
14
15// O(n log n) — patience sorting with binary search
16public int lengthOfLISOptimal(int[] nums) {
17 List<Integer> tails = new ArrayList<>();
18 for (int num : nums) {
19 int pos = Collections.binarySearch(tails, num);
20 if (pos < 0) pos = -(pos + 1);
21 if (pos == tails.size()) tails.add(num);
22 else tails.set(pos, num);
23 }
24 return tails.size();
25}More in DSA