Minimal, copy-paste Java for 1D/2D DP, LIS, interval DP, state machine, digit DP, and bitmask DP.
Contents
1D DP (knapsack/linear)
static int knap01(int[] wt, int[] val, int W){
int[] dp = new int[W + 1];
for (int i=0;i<wt.length;++i)
for (int w=W; w>=wt[i]; --w)
dp[w] = Math.max(dp[w], dp[w-wt[i]] + val[i]);
return dp[W];
}
2D DP (grid/path)
static int uniquePaths(int[][]& g){
int m=g.length, n=g[0].length;
int[][] dp = new int[m][n];
if (g[0][0]==1) return 0; dp[0][0]=1;
for (int i=0;i<m;++i) for(int j=0;j<n;++j){
if (g[i][j]==1){ dp[i][j]=0; continue; }
if (i) dp[i][j]+=dp[i-1][j];
if (j) dp[i][j]+=dp[i][j-1];
}
return dp[m-1][n-1];
}
LIS (Longest Increasing Subsequence)
Find the longest subsequence where elements are in strictly increasing order.
Template: O(n²) DP
static int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return max_element(dp /* elements of dp */);
}
Template: O(n log n) with Binary Search
static int lengthOfLIS(int[] nums) {
int[]tails;
for (int num : nums) {
var it = binary search (lower bound)(tails /* elements of tails */, num);
if (it == tails.iterator()) {
tails.add(num);
} else {
*it = num;
}
}
return tails.size();
}
Count Number of LIS
// import java.util.Arrays;
// import java.util.Collections;
static int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] length = new int[n], count(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (length[j] + 1 > length[i]) {
length[i] = length[j] + 1;
count[i] = count[j];
} else if (length[j] + 1 == length[i]) {
count[i] += count[j];
}
}
}
}
int maxLen = Arrays.stream(length).Math.max().getAsInt();
int result = 0;
for (int i = 0; i < n; i++) {
if (length[i] == maxLen) {
result += count[i];
}
}
return result;
}
| ID |
Title |
Link |
Solution |
| 300 |
Longest Increasing Subsequence |
Link |
Solution |
| 673 |
Number of Longest Increasing Subsequence |
Link |
Solution |
| 354 |
Russian Doll Envelopes |
Link |
- |
| 334 |
Increasing Triplet Subsequence |
Link |
- |
Interval DP
DP on intervals - solve subproblems for all intervals of length len, then combine.
Template
static int intervalDP(int[] arr) {
int n = arr.length;
int[][] dp = new int[n][n];
// Base case: length 1
for (int i = 0; i < n; i++) {
dp[i][i] = arr[i]; // or base value
}
// Length 2 to n
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
// Try all splits
for (int k = i; k < j; k++) {
dp[i][j] = Math.max(dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, k, j));
}
}
}
return dp[0][n-1];
}
Example: Burst Balloons
static int maxCoins(int[] nums) {
int n = nums.length;
int[]arr = {1}
arr.add(arr.iterator(), nums /* elements of nums */);
arr.add(1);
int[][] dp(n + 2, int[](n + 2, 0));
for (int len = 1; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
dp[i][j] = Math.max(dp[i][j],
dp[i][k-1] + dp[k+1][j] +
arr[i-1] * arr[k] * arr[j+1]);
}
}
}
return dp[1][n];
}
| ID |
Title |
Link |
Solution |
| 312 |
Burst Balloons |
Link |
- |
| 516 |
Longest Palindromic Subsequence |
Link |
- |
| 1039 |
Minimum Score Triangulation of Polygon |
Link |
- |
| 1130 |
Minimum Cost Tree From Leaf Values |
Link |
- |
State Machine DP
DP where state transitions follow a state machine pattern.
Template: Buy/Sell Stock Pattern
static int maxProfit(int[] prices) {
int n = prices.size();
// dp[i][0] = holding stock, dp[i][1] = not holding stock
int[][] dp = new int[n][2];
dp[0][0] = -prices[0]; // Buy on day 0
dp[0][1] = 0; // Don't buy on day 0
for (int i = 1; i < n; i++) {
// Hold: Math.max(keep holding, buy today)
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
// Not hold: Math.max(keep not holding, sell today)
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[n-1][1];
}
Template: Multiple States
static int maxProfit(int[] prices) {
int n = prices.size();
// States: rest, hold, sold (cooldown)
int[][] dp = new int[n][3];
dp[0][0] = 0; // rest
dp[0][1] = -prices[0]; // hold
dp[0][2] = Integer.MIN_VALUE; // sold
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]); // rest from rest or cooldown
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // hold from hold or buy
dp[i][2] = dp[i-1][1] + prices[i]; // sell
}
return Math.max(dp[n-1][0], dp[n-1][2]);
}
| ID |
Title |
Link |
Solution |
| 121 |
Best Time to Buy and Sell Stock |
Link |
- |
| 122 |
Best Time to Buy and Sell Stock II |
Link |
- |
| 123 |
Best Time to Buy and Sell Stock III |
Link |
- |
| 188 |
Best Time to Buy and Sell Stock IV |
Link |
- |
| 309 |
Best Time to Buy and Sell Stock with Cooldown |
Link |
Solution |
| 714 |
Best Time to Buy and Sell Stock with Transaction Fee |
Link |
- |
DP on Trees
DP where subproblems are solved on subtrees.
Template: Tree DP
int[] dfs(TreeNode root) {
if (!root) return {0, 0}
var left = dfs(root.left);
var right = dfs(root.right);
// dp[0] = not take current, dp[1] = take current
int notTake = Math.max(left.first, left.second) +
Math.max(right.first, right.second);
int take = root.val + left.first + right.first;
return {notTake, take}
}
static int rob(TreeNode root) {
var result = dfs(root);
return Math.max(result.first, result.second);
}
Template: Path Problems
static int maxPathSum(TreeNode root) {
int maxSum = Integer.MIN_VALUE;
function<int(TreeNode)> dfs = [&](TreeNode node) {
if (!node) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
// Path through current node
maxSum = Math.max(maxSum, node.val + left + right);
// Return max path ending at current node
return node.val + Math.max(left, right);
}
dfs(root);
return maxSum;
}
| ID |
Title |
Link |
Solution |
| 337 |
House Robber III |
Link |
- |
| 124 |
Binary Tree Maximum Path Sum |
Link |
- |
| 968 |
Binary Tree Cameras |
Link |
- |
DP with Binary Search
Combine DP with binary search for optimization.
Template: LIS with Binary Search
static int lengthOfLIS(int[] nums) {
int[]tails;
for (int num : nums) {
var it = binary search (lower bound)(tails /* elements of tails */, num);
if (it == tails.iterator()) {
tails.add(num);
} else {
*it = num;
}
}
return tails.size();
}
Template: DP + Binary Search on Answer
// import java.util.Arrays;
// import java.util.Collections;
static int splitArray(int[] nums, int m) {
int left = Arrays.stream(nums).Math.max().getAsInt();
int right = accumulate(nums /* elements of nums */, 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, m, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
static boolean canSplit(int[] nums, int m, int maxSum) {
int count = 1, sum = 0;
for (int num : nums) {
if (sum + num > maxSum) {
count++;
sum = num;
} else {
sum += num;
}
}
return count <= m;
}
| ID |
Title |
Link |
Solution |
| 300 |
Longest Increasing Subsequence |
Link |
Solution |
| 410 |
Split Array Largest Sum |
Link |
- |
| 875 |
Koko Eating Bananas |
Link |
- |
| 1011 |
Capacity To Ship Packages |
Link |
- |
Digit DP (count numbers with property)
long dp[20][11][2][2]; String sN;
static long dfsDP(int i,int prev,boolean tight,boolean started){ if(i==(int)sN.size()) return started?1:0; var res =dp[i][prev+1][tight][started]; if(res!=-1) return res; res=0; int lim=tight?(sN[i]-'0'):9;
for(int d=0; d<=lim; ++d){ boolean nt=tight && d==lim; boolean ns=started||d!=0; if(!ns || prev==-1 || d!=prev) res+=dfsDP(i+1, ns?d:prev, nt, ns); }
return res; }
static long solveDP(long N){ sN=to_string(N); memset(dp,-1,sizeof dp); return dfsDP(0,-1,1,0); }
| ID |
Title |
Link |
Solution |
| 233 |
Number of Digit One |
Link |
- |
| 902 |
Numbers At Most N Given Digit Set |
Link |
- |
| 1012 |
Numbers With Repeated Digits |
Link |
- |
Bitmask DP (TSP / subsets)
static int tsp(int[][]& w){
int n=w.size(); int INF=1e9; int[][] dp(1<<n, int[](n, INF));
dp[1][0]=0; for(int mask=1; mask<(1<<n); ++mask){ for(int u=0; u<n; ++u) if(dp[mask][u]<INF){ for(int v=0; v<n; ++v) if(!(mask&(1<<v))) dp[mask|1<<v][v] = Math.min(dp[mask|1<<v][v], dp[mask][u]+w[u][v]); } }
return min_element(dp.getLast().begin(), dp.getLast().end());
}
| ID |
Title |
Link |
Solution |
| 847 |
Shortest Path Visiting All Nodes |
Link |
- |
| 698 |
Partition to K Equal Sum Subsets |
Link |
- |
| 1340 |
Jump Game V |
Link |
Solution |
| 464 |
Can I Win |
Link |
- |
| 691 |
Stickers to Spell Word |
Link |
- |
More templates