Dynamic Programming — Java

Recursion · Memoization · Tabulation | TUF+ DSA Checklist

■ 1D Dynamic Programming

1. Climbing Stairs
Recursion
int climbStairs(int n) {
if (n <= 1) return 1;
return climbStairs(n - 1) + climbStairs(n - 2);
}

Memoization
int climbStairs(int n, int[] memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n];
return memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
}

Tabulation
int climbStairs(int n) {
if (n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}

2. Frog Jump (Min Cost)

Recursion
int frogJump(int n, int[] h) {
if (n == 0) return 0;
int left = frogJump(n - 1, h) + [Link](h[n] - h[n-1]);
int right = (n > 1) ? frogJump(n - 2, h) + [Link](h[n] - h[n-2])
: Integer.MAX_VALUE;
return [Link](left, right);
}

Memoization
int frogJump(int n, int[] h, int[] dp) {
if (n == 0) return 0;
if (dp[n] != -1) return dp[n];
int left = frogJump(n-1, h, dp) + [Link](h[n] - h[n-1]);
int right = (n > 1) ? frogJump(n-2, h, dp) + [Link](h[n] - h[n-2])
: Integer.MAX_VALUE;
return dp[n] = [Link](left, right);
}

Tabulation
int frogJump(int[] h) {
int n = [Link];
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
int left = dp[i-1] + [Link](h[i] - h[i-1]);
int right = (i > 1) ? dp[i-2] + [Link](h[i] - h[i-2]) : Integer.MAX_VALUE;
dp[i] = [Link](left, right);
}
return dp[n - 1];
}

3. Frog Jump with K Distances

Memoization
int frogK(int n, int k, int[] h, int[] dp) {
if (n == 0) return 0;
if (dp[n] != -1) return dp[n];
int best = Integer.MAX_VALUE;
for (int j = 1; j <= k && n - j >= 0; j++) {
int cost = frogK(n - j, k, h, dp) + [Link](h[n] - h[n - j]);
best = [Link](best, cost);
}
return dp[n] = best;
}

Tabulation
int frogK(int[] h, int k) {
int n = [Link];
int[] dp = new int[n];
[Link](dp, Integer.MAX_VALUE); dp[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 1; j <= k && i - j >= 0; j++)
dp[i] = [Link](dp[i], dp[i-j] + [Link](h[i] - h[i-j]));
return dp[n - 1];
}

4. Maximum Sum of Non-Adjacent Elements (House Robber I)

Recursion
int rob(int i, int[] nums) {
if (i < 0) return 0;
if (i == 0) return nums[0];
return [Link](nums[i] + rob(i - 2, nums), rob(i - 1, nums));
}

Memoization
int rob(int i, int[] nums, int[] dp) {
if (i < 0) return 0;
if (i == 0) return nums[0];
if (dp[i] != -1) return dp[i];
return dp[i] = [Link](nums[i] + rob(i-2, nums, dp), rob(i-1, nums, dp));
}

Tabulation
int rob(int[] nums) {
int n = [Link];
if (n == 1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0]; dp[1] = [Link](nums[0], nums[1]);
for (int i = 2; i < n; i++)
dp[i] = [Link](dp[i-1], nums[i] + dp[i-2]);
return dp[n - 1];
}

5. House Robber II (Circular)

Tabulation
int rob(int[] nums) {
int n = [Link];
if (n == 1) return nums[0];
return [Link](robRange(nums, 0, n-2), robRange(nums, 1, n-1));
}
int robRange(int[] nums, int lo, int hi) {
int prev2 = 0, prev1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = [Link](prev1, nums[i] + prev2);
prev2 = prev1; prev1 = cur;
}
return prev1;
}

■ 2D Dynamic Programming

6. Ninja's Training
Memoization
int solve(int day, int last, int[][] pts, int[][] dp) {
if (day < 0) return 0;
if (dp[day][last] != -1) return dp[day][last];
int best = 0;
for (int task = 0; task < 3; task++)
if (task != last)
best = [Link](best, pts[day][task] + solve(day-1, task, pts, dp));
return dp[day][last] = best;
}

Tabulation
int ninjaTraining(int[][] pts) {
int n = [Link];
int[][] dp = new int[n][4];
dp[0][0] = [Link](pts[0][1], pts[0][2]);
dp[0][1] = [Link](pts[0][0], pts[0][2]);
dp[0][2] = [Link](pts[0][0], pts[0][1]);
dp[0][3] = [Link](pts[0][0], [Link](pts[0][1], pts[0][2]));
for (int day = 1; day < n; day++)
for (int last = 0; last < 4; last++)
for (int task = 0; task < 3; task++)
if (task != last)
dp[day][last] = [Link](dp[day][last], pts[day][task] + dp[day-1][task]);
return dp[n-1][3];
}

7. Unique Paths in a Grid

Recursion
int uniquePaths(int m, int n) {
if (m == 1 || n == 1) return 1;
return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

Memoization
int uniquePaths(int m, int n, int[][] dp) {
if (m == 1 || n == 1) return 1;
if (dp[m][n] != -1) return dp[m][n];
return dp[m][n] = uniquePaths(m-1, n, dp) + uniquePaths(m, n-1, dp);
}

Tabulation
int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int[] row : dp) [Link](row, 1);
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}

8. Unique Paths II (with Obstacles)

Memoization
int solve(int i, int j, int[][] grid, int[][] dp) {
if (i < 0 || j < 0 || grid[i][j] == 1) return 0;
if (i == 0 && j == 0) return 1;
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = solve(i-1, j, grid, dp) + solve(i, j-1, grid, dp);
}

Tabulation
int uniquePathsWithObstacles(int[][] grid) {
int m = [Link], n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = (grid[0][0] == 0) ? 1 : 0;
for (int i = 1; i < m; i++) dp[i][0] = (grid[i][0] == 0) ? dp[i-1][0] : 0;
for (int j = 1; j < n; j++) dp[0][j] = (grid[0][j] == 0) ? dp[0][j-1] : 0;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = (grid[i][j] == 1) ? 0 : dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}

9. Minimum Falling Path Sum

Memoization
int solve(int i, int j, int[][] mat, int[][] dp) {
if (j < 0 || j >= mat[0].length) return (int)1e9;
if (i == 0) return mat[0][j];
if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
int up = solve(i-1, j, mat, dp);
int ul = solve(i-1, j-1, mat, dp);
int ur = solve(i-1, j+1, mat, dp);
return dp[i][j] = mat[i][j] + [Link](up, [Link](ul, ur));
}

Tabulation
int minFallingPathSum(int[][] mat) {
int n = [Link];
int[][] dp = new int[n][n];
dp[0] = mat[0].clone();
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++) {
int up = dp[i-1][j];
int ul = (j > 0) ? dp[i-1][j-1] : (int)1e9;
int ur = (j < n-1) ? dp[i-1][j+1] : (int)1e9;
dp[i][j] = mat[i][j] + [Link](up, [Link](ul, ur));
}
int ans = Integer.MAX_VALUE;
for (int v : dp[n-1]) ans = [Link](ans, v);
return ans;
}

10. Triangle (Min Path Sum)

Memoization
int solve(int i, int j, List<List<Integer>> tri, int[][] dp) {
int n = [Link]();
if (i == n-1) return [Link](i).get(j);
if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
int down = solve(i+1, j, tri, dp);
int diag = solve(i+1, j+1, tri, dp);
return dp[i][j] = [Link](i).get(j) + [Link](down, diag);
}

Tabulation
int minimumTotal(List<List<Integer>> tri) {
int n = [Link]();
int[] dp = new ArrayList<>([Link](n-1)).stream()
.mapToInt(Integer::intValue).toArray();
for (int i = n-2; i >= 0; i--)
for (int j = 0; j <= i; j++)
dp[j] = [Link](i).get(j) + [Link](dp[j], dp[j+1]);
return dp[0];
}

11. Cherry Pickup II

Memoization
int solve(int r, int c1, int c2, int[][] g, int[][][] dp) {
int n = g[0].length;
if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n) return (int)-1e9;
if (r == [Link]) return 0;
if (dp[r][c1][c2] != -1) return dp[r][c1][c2];
int cherries = g[r][c1] + (c1 != c2 ? g[r][c2] : 0);
int best = (int)-1e9;
for (int d1 = -1; d1 <= 1; d1++)
for (int d2 = -1; d2 <= 1; d2++)
best = [Link](best, solve(r+1, c1+d1, c2+d2, g, dp));
return dp[r][c1][c2] = cherries + best;
}

Tabulation
int cherryPickup(int[][] g) {
int m = [Link], n = g[0].length;
int[][][] dp = new int[m][n][n];
for (int c1 = 0; c1 < n; c1++)
for (int c2 = 0; c2 < n; c2++)
dp[m-1][c1][c2] = g[m-1][c1] + (c1 != c2 ? g[m-1][c2] : 0);
for (int r = m-2; r >= 0; r--)
for (int c1 = 0; c1 < n; c1++)
for (int c2 = 0; c2 < n; c2++) {
int cherries = g[r][c1] + (c1 != c2 ? g[r][c2] : 0), best = (int)-1e9;
for (int d1 = -1; d1 <= 1; d1++)
for (int d2 = -1; d2 <= 1; d2++) {
int nc1 = c1+d1, nc2 = c2+d2;
if (nc1 >= 0 && nc1 < n && nc2 >= 0 && nc2 < n)
best = [Link](best, dp[r+1][nc1][nc2]);
}
dp[r][c1][c2] = cherries + best;
}
return dp[0][0][n-1];
}

■ DP on Stocks

12. Best Time to Buy and Sell Stock I

Tabulation / Greedy
int maxProfit(int[] prices) {
int minP = Integer.MAX_VALUE, ans = 0;
for (int p : prices) {
minP = [Link](minP, p);
ans = [Link](ans, p - minP);
}
return ans;
}

13. Best Time to Buy and Sell Stock II (Unlimited Transactions)

Memoization
int dp(int i, int buy, int[] prices, int[][] memo) {
if (i == [Link]) return 0;
if (memo[i][buy] != -1) return memo[i][buy];
if (buy == 1)
return memo[i][buy] = [Link](-prices[i] + dp(i+1, 0, prices, memo),
dp(i+1, 1, prices, memo));
return memo[i][buy] = [Link](prices[i] + dp(i+1, 1, prices, memo),
dp(i+1, 0, prices, memo));
}

Tabulation
int maxProfit(int[] prices) {
int n = [Link];
int[][] dp = new int[n+1][2];
for (int i = n-1; i >= 0; i--) {
dp[i][1] = [Link](-prices[i] + dp[i+1][0], dp[i+1][1]);
dp[i][0] = [Link](prices[i] + dp[i+1][1], dp[i+1][0]);
}
return dp[0][1];
}

14. Best Time to Buy and Sell Stock III (At Most 2 Transactions)
Memoization
int dp(int i, int buy, int cap, int[] p, int[][][] memo) {
if (i == [Link] || cap == 0) return 0;
if (memo[i][buy][cap] != -1) return memo[i][buy][cap];
if (buy == 1)
return memo[i][buy][cap] = [Link](-p[i] + dp(i+1,0,cap,p,memo),
dp(i+1,1,cap,p,memo));
return memo[i][buy][cap] = [Link](p[i] + dp(i+1,1,cap-1,p,memo),
dp(i+1,0,cap,p,memo));
}

Tabulation
int maxProfit(int[] prices) {
int n = [Link];
int[][][] dp = new int[n+1][2][3];
for (int i = n-1; i >= 0; i--)
for (int cap = 1; cap <= 2; cap++) {
dp[i][1][cap] = [Link](-prices[i]+dp[i+1][0][cap], dp[i+1][1][cap]);
dp[i][0][cap] = [Link](prices[i]+dp[i+1][1][cap-1], dp[i+1][0][cap]);
}
return dp[0][1][2];
}

15. Best Time to Buy and Sell Stock IV (At Most K Transactions)
Tabulation
int maxProfit(int k, int[] prices) {
int n = [Link];
int[][][] dp = new int[n+1][2][k+1];
for (int i = n-1; i >= 0; i--)
for (int cap = 1; cap <= k; cap++) {
dp[i][1][cap] = [Link](-prices[i]+dp[i+1][0][cap], dp[i+1][1][cap]);
dp[i][0][cap] = [Link](prices[i]+dp[i+1][1][cap-1], dp[i+1][0][cap]);
}
return dp[0][1][k];
}

16. Best Time to Buy and Sell Stock with Transaction Fee
Tabulation
int maxProfit(int[] prices, int fee) {
int n = [Link];
int[][] dp = new int[n+1][2];
for (int i = n-1; i >= 0; i--) {
dp[i][1] = [Link](-prices[i]+dp[i+1][0], dp[i+1][1]);
dp[i][0] = [Link](prices[i]-fee+dp[i+1][1], dp[i+1][0]);
}
return dp[0][1];
}

■ DP on Subsequences

17. Subset Sum Equals Target

Recursion
boolean subsetSum(int i, int target, int[] nums) {
if (target == 0) return true;
if (i == 0) return nums[0] == target;
boolean notTake = subsetSum(i-1, target, nums);
boolean take = (nums[i] <= target) && subsetSum(i-1, target-nums[i], nums);
return take || notTake;
}

Memoization
boolean solve(int i, int t, int[] nums, Boolean[][] dp) {
if (t == 0) return true;
if (i == 0) return nums[0] == t;
if (dp[i][t] != null) return dp[i][t];
boolean nt = solve(i-1, t, nums, dp);
boolean tk = (nums[i] <= t) && solve(i-1, t-nums[i], nums, dp);
return dp[i][t] = tk || nt;
}

Tabulation
boolean subsetSum(int[] nums, int target) {
int n = [Link];
boolean[][] dp = new boolean[n][target+1];
for (int i = 0; i < n; i++) dp[i][0] = true;
if (nums[0] <= target) dp[0][nums[0]] = true;
for (int i = 1; i < n; i++)
for (int t = 1; t <= target; t++)
dp[i][t] = dp[i-1][t] || (nums[i] <= t && dp[i-1][t-nums[i]]);
return dp[n-1][target];
}

18. Partition Equal Subset Sum

Tabulation
boolean canPartition(int[] nums) {
int sum = 0; for (int x : nums) sum += x;
if (sum % 2 != 0) return false;
int target = sum / 2, n = [Link];
boolean[][] dp = new boolean[n][target+1];
for (int i = 0; i < n; i++) dp[i][0] = true;
if (nums[0] <= target) dp[0][nums[0]] = true;
for (int i = 1; i < n; i++)
for (int t = 1; t <= target; t++)
dp[i][t] = dp[i-1][t] || (nums[i] <= t && dp[i-1][t-nums[i]]);
return dp[n-1][target];
}

19. Partition Into Two Subsets with Minimum Absolute Difference

Tabulation
int minimumDifference(int[] nums) {
int n = [Link], total = 0;
for (int x : nums) total += x;
int target = total / 2;
boolean[][] dp = new boolean[n][target+1];
for (int i = 0; i < n; i++) dp[i][0] = true;
if (nums[0] <= target) dp[0][nums[0]] = true;
for (int i = 1; i < n; i++)
for (int t = 1; t <= target; t++)
dp[i][t] = dp[i-1][t] || (nums[i] <= t && dp[i-1][t-nums[i]]);
for (int t = target; t >= 0; t--)
if (dp[n-1][t]) return [Link](total - 2*t);
return 0;
}

20. Count Subsets with Sum K

Tabulation
int countSubsets(int[] nums, int target) {
int n = [Link];
int[][] dp = new int[n][target+1];
for (int i = 0; i < n; i++) dp[i][0] = 1;
if (nums[0] <= target) dp[0][nums[0]] = 1;
for (int i = 1; i < n; i++)
for (int t = 0; t <= target; t++)
dp[i][t] = dp[i-1][t] + (nums[i] <= t ? dp[i-1][t-nums[i]] : 0);
return dp[n-1][target];
}

21. Count Partitions with Given Difference

Tabulation
int countPartitions(int[] nums, int d) {
int total = 0; for (int x : nums) total += x;
if ((total - d) < 0 || (total - d) % 2 != 0) return 0;
int target = (total - d) / 2, n = [Link];
int[][] dp = new int[n][target+1];
for (int i = 0; i < n; i++) dp[i][0] = 1;
if (nums[0] <= target) dp[0][nums[0]] += 1;
for (int i = 1; i < n; i++)
for (int t = 0; t <= target; t++)
dp[i][t] = dp[i-1][t] + (nums[i] <= t ? dp[i-1][t-nums[i]] : 0);
return dp[n-1][target];
}

22. 0/1 Knapsack

Recursion
int knapsack(int i, int W, int[] wt, int[] val) {
if (i == 0) return (wt[0] <= W) ? val[0] : 0;
int notTake = knapsack(i-1, W, wt, val);
int take = (wt[i] <= W) ? val[i] + knapsack(i-1, W-wt[i], wt, val) : 0;
return [Link](take, notTake);
}

Memoization
int knapsack(int i, int W, int[] wt, int[] val, int[][] dp) {
if (i == 0) return (wt[0] <= W) ? val[0] : 0;
if (dp[i][W] != -1) return dp[i][W];
int nt = knapsack(i-1, W, wt, val, dp);
int tk = (wt[i] <= W) ? val[i] + knapsack(i-1, W-wt[i], wt, val, dp) : 0;
return dp[i][W] = [Link](tk, nt);
}

Tabulation
int knapsack(int[] wt, int[] val, int W) {
int n = [Link];
int[][] dp = new int[n][W+1];
for (int w = wt[0]; w <= W; w++) dp[0][w] = val[0];
for (int i = 1; i < n; i++)
for (int w = 0; w <= W; w++) {
int nt = dp[i-1][w];
int tk = (wt[i] <= w) ? val[i] + dp[i-1][w-wt[i]] : 0;
dp[i][w] = [Link](tk, nt);
}
return dp[n-1][W];
}

23. Coin Change (Minimum Coins)

Recursion
int coinChange(int i, int amount, int[] coins) {
if (amount == 0) return 0;
if (i == 0) return (amount % coins[0] == 0) ? amount/coins[0] : (int)1e9;
int notTake = coinChange(i-1, amount, coins);
int take = (coins[i] <= amount)
? 1 + coinChange(i, amount - coins[i], coins) : (int)1e9;
return [Link](take, notTake);
}

Memoization
int coinChange(int i, int amt, int[] coins, int[][] dp) {
if (amt == 0) return 0;
if (i == 0) return (amt % coins[0] == 0) ? amt/coins[0] : (int)1e9;
if (dp[i][amt] != -1) return dp[i][amt];
int nt = coinChange(i-1, amt, coins, dp);
int tk = (coins[i] <= amt) ? 1 + coinChange(i, amt-coins[i], coins, dp) : (int)1e9;
return dp[i][amt] = [Link](tk, nt);
}

Tabulation
int coinChange(int[] coins, int amount) {
int n = [Link], INF = (int)1e9;
int[][] dp = new int[n][amount+1];
for (int a = 0; a <= amount; a++)
dp[0][a] = (a % coins[0] == 0) ? a/coins[0] : INF;
for (int i = 1; i < n; i++)
for (int a = 0; a <= amount; a++) {
int nt = dp[i-1][a];
int tk = (coins[i] <= a) ? 1 + dp[i][a-coins[i]] : INF;
dp[i][a] = [Link](tk, nt);
}
return dp[n-1][amount] >= INF ? -1 : dp[n-1][amount];
}
24. Target Sum
Memoization
int dp(int i, int cur, int target, int[] nums, HashMap<String,Integer> memo) {
if (i == [Link]) return cur == target ? 1 : 0;
String key = i + "," + cur;
if ([Link](key)) return [Link](key);
int res = dp(i+1, cur+nums[i], target, nums, memo)
+ dp(i+1, cur-nums[i], target, nums, memo);
[Link](key, res); return res;
}

Tabulation (Subset Count)

int findTargetSumWays(int[] nums, int target) {
int total = 0; for (int x : nums) total += x;
if ((total + target) % 2 != 0 || [Link](target) > total) return 0;
int s = (total + target) / 2, n = [Link];
int[][] dp = new int[n+1][s+1]; dp[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int t = 0; t <= s; t++)
dp[i][t] = dp[i-1][t] + (nums[i-1] <= t ? dp[i-1][t-nums[i-1]] : 0);
return dp[n][s];
}

25. Coin Change II (Count Ways)

Memoization
int dp(int i, int amount, int[] coins, int[][] memo) {
if (amount == 0) return 1;
if (i == 0) return (amount % coins[0] == 0) ? 1 : 0;
if (memo[i][amount] != -1) return memo[i][amount];
int nt = dp(i-1, amount, coins, memo);
int tk = (coins[i] <= amount) ? dp(i, amount-coins[i], coins, memo) : 0;
return memo[i][amount] = tk + nt;
}

Tabulation
int change(int amount, int[] coins) {
int n = [Link];
int[][] dp = new int[n][amount+1];
for (int a = 0; a <= amount; a++) dp[0][a] = (a % coins[0] == 0) ? 1 : 0;
for (int i = 1; i < n; i++)
for (int a = 0; a <= amount; a++)
dp[i][a] = dp[i-1][a] + (coins[i] <= a ? dp[i][a-coins[i]] : 0);
return dp[n-1][amount];
}

26. Unbounded Knapsack

Memoization
int dp(int i, int W, int[] wt, int[] val, int[][] memo) {
if (i == 0) return (W / wt[0]) * val[0];
if (memo[i][W] != -1) return memo[i][W];
int nt = dp(i-1, W, wt, val, memo);
int tk = (wt[i] <= W) ? val[i] + dp(i, W-wt[i], wt, val, memo) : 0;
return memo[i][W] = [Link](tk, nt);
}

Tabulation
int unboundedKnapsack(int[] wt, int[] val, int W) {
int n = [Link];
int[][] dp = new int[n][W+1];
for (int w = 0; w <= W; w++) dp[0][w] = (w / wt[0]) * val[0];
for (int i = 1; i < n; i++)
for (int w = 0; w <= W; w++) {
int nt = dp[i-1][w];
int tk = (wt[i] <= w) ? val[i] + dp[i][w-wt[i]] : 0;
dp[i][w] = [Link](tk, nt);
}
return dp[n-1][W];
}

27. Rod Cutting Problem

Memoization
int dp(int i, int length, int[] price, int[][] memo) {
if (i == 0) return length * price[0];
if (memo[i][length] != -1) return memo[i][length];
int nt = dp(i-1, length, price, memo);
int tk = ((i+1) <= length) ? price[i] + dp(i, length-(i+1), price, memo) : 0;
return memo[i][length] = [Link](tk, nt);
}

Tabulation
int rodCutting(int[] price, int n) {
int[][] dp = new int[n][n+1];
for (int len = 0; len <= n; len++) dp[0][len] = len * price[0];
for (int i = 1; i < n; i++)
for (int len = 0; len <= n; len++) {
int nt = dp[i-1][len];
int tk = ((i+1) <= len) ? price[i] + dp[i][len-(i+1)] : 0;
dp[i][len] = [Link](tk, nt);
}
return dp[n-1][n];
}

■ LIS — Longest Increasing Subsequence Variants

28. Longest Increasing Subsequence (LIS)

Recursion
int solve(int i, int prev, int[] nums) {
if (i == [Link]) return 0;
int take = 0;
if (prev == -1 || nums[i] > nums[prev])
take = 1 + solve(i+1, i, nums);
return [Link](take, solve(i+1, prev, nums));
}

Memoization
int dp(int i, int prev, int[] nums, int[][] memo) {
if (i == [Link]) return 0;
if (memo[i][prev+1] != -1) return memo[i][prev+1];
int take = 0;
if (prev == -1 || nums[i] > nums[prev])
take = 1 + dp(i+1, i, nums, memo);
return memo[i][prev+1] = [Link](take, dp(i+1, prev, nums, memo));
}

Tabulation
int lengthOfLIS(int[] nums) {
int n = [Link], ans = 1;
int[] dp = new int[n]; [Link](dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) dp[i] = [Link](dp[i], dp[j]+1);
ans = [Link](ans, dp[i]);
}
return ans;
}

29. Print LIS

Tabulation + Backtrack
List<Integer> printLIS(int[] nums) {
int n = [Link];
int[] dp = new int[n], parent = new int[n];
[Link](dp, 1); [Link](parent, -1);
int maxLen = 1, idx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; parent[i]=j; }
if (dp[i] > maxLen) { maxLen = dp[i]; idx = i; }
}
List<Integer> lis = new ArrayList<>();
while (idx != -1) { [Link](nums[idx]); idx = parent[idx]; }
[Link](lis); return lis;
}

30. Largest Divisible Subset

Tabulation
List<Integer> largestDivisibleSubset(int[] nums) {
[Link](nums); int n = [Link];
int[] dp = new int[n], parent = new int[n];
[Link](dp, 1); [Link](parent, -1);
int maxLen = 1, idx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[i] % nums[j] == 0 && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; parent[i]=j; }
if (dp[i] > maxLen) { maxLen = dp[i]; idx = i; }
}
List<Integer> res = new ArrayList<>();
while (idx != -1) { [Link](nums[idx]); idx = parent[idx]; }
[Link](res); return res;
}

31. Longest String Chain

Tabulation
int longestStrChain(String[] words) {
[Link](words, [Link](String::length));
Map<String,Integer> dp = new HashMap<>();
int ans = 1;
for (String w : words) {
[Link](w, 1);
for (int i = 0; i < [Link](); i++) {
String pred = [Link](0,i) + [Link](i+1);
if ([Link](pred))
[Link](w, [Link]([Link](w), [Link](pred)+1));
}
ans = [Link](ans, [Link](w));
}
return ans;
}

32. Longest Bitonic Subsequence

Tabulation
int longestBitonicSubsequence(int[] nums) {
int n = [Link];
int[] inc = new int[n], dec = new int[n];
[Link](inc, 1); [Link](dec, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) inc[i] = [Link](inc[i], inc[j]+1);
for (int i = n-2; i >= 0; i--)
for (int j = i+1; j < n; j++)
if (nums[j] < nums[i]) dec[i] = [Link](dec[i], dec[j]+1);
int ans = 0;
for (int i = 0; i < n; i++) ans = [Link](ans, inc[i]+dec[i]-1);
return ans;
}

33. Number of Longest Increasing Subsequences

Tabulation
int findNumberOfLIS(int[] nums) {
int n = [Link];
int[] dp = new int[n], cnt = new int[n];
[Link](dp, 1); [Link](cnt, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; cnt[i]=cnt[j]; }
else if (dp[j]+1 == dp[i]) cnt[i] += cnt[j];
}
}
maxLen = [Link](maxLen, dp[i]);
}
int res = 0;
for (int i = 0; i < n; i++) if (dp[i] == maxLen) res += cnt[i];
return res;
}

■ DP on Strings

34. Longest Common Subsequence (LCS)

Recursion
int lcs(int i, int j, String s1, String s2) {
if (i < 0 || j < 0) return 0;
if ([Link](i) == [Link](j)) return 1 + lcs(i-1, j-1, s1, s2);
return [Link](lcs(i-1, j, s1, s2), lcs(i, j-1, s1, s2));
}

Memoization
int dp(int i, int j, String s1, String s2, int[][] memo) {
if (i < 0 || j < 0) return 0;
if (memo[i][j] != -1) return memo[i][j];
if ([Link](i) == [Link](j)) return memo[i][j] = 1 + dp(i-1,j-1,s1,s2,memo);
return memo[i][j] = [Link](dp(i-1,j,s1,s2,memo), dp(i,j-1,s1,s2,memo));
}

Tabulation
int lcs(String s1, String s2) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if ([Link](i-1) == [Link](j-1)) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
return dp[m][n];
}

35. Longest Common Substring

Tabulation
int longestCommonSubstring(String s1, String s2) {
int m = [Link](), n = [Link](), ans = 0;
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1))
ans = [Link](ans, dp[i][j] = 1 + dp[i-1][j-1]);
else dp[i][j] = 0;
}
return ans;
}

36. Longest Palindromic Subsequence

Tabulation (via LCS with reverse)
int longestPalindromeSubseq(String s) {
String t = new StringBuilder(s).reverse().toString();
int n = [Link]();
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if ([Link](i-1) == [Link](j-1)) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
return dp[n][n];
}

37. Minimum Insertions to Make String Palindrome

Tabulation
int minInsertions(String s) {
int n = [Link]();
// answer = n - LPS
String t = new StringBuilder(s).reverse().toString();
int[][] dp = new int[n+1][n+1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if ([Link](i-1) == [Link](j-1)) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
return n - dp[n][n];
}

38. Min Insertions/Deletions to Convert String A to B

Tabulation
int minDistance(String s1, String s2) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if ([Link](i-1) == [Link](j-1)) dp[i][j] = 1 + dp[i-1][j-1];
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
int lcs = dp[m][n];
return (m - lcs) + (n - lcs);
}
39. Shortest Common Supersequence
Tabulation
String shortestCommonSupersequence(String s1, String s2) {
int m=[Link](), n=[Link]();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
if([Link](i-1)==[Link](j-1)) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=[Link](dp[i-1][j],dp[i][j-1]);
StringBuilder sb = new StringBuilder();
int i=m, j=n;
while(i>0 && j>0) {
if([Link](i-1)==[Link](j-1)) { [Link]([Link](i-1)); i--; j--; }
else if(dp[i-1][j] > dp[i][j-1]) [Link]([Link](--i));
else [Link]([Link](--j));
}
while(i>0) [Link]([Link](--i));
while(j>0) [Link]([Link](--j));
return [Link]().toString();
}

40. Distinct Subsequences

Memoization
long dp(int i, int j, String s, String t, long[][] memo) {
if (j < 0) return 1;
if (i < 0) return 0;
if (memo[i][j] != -1) return memo[i][j];
if ([Link](i) == [Link](j))
return memo[i][j] = dp(i-1,j-1,s,t,memo) + dp(i-1,j,s,t,memo);
return memo[i][j] = dp(i-1,j,s,t,memo);
}

Tabulation
int numDistinct(String s, String t) {
int m=[Link](), n=[Link]();
long[][] dp = new long[m+1][n+1];
for (int i=0;i<=m;i++) dp[i][0]=1;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++) {
dp[i][j]=dp[i-1][j];
if ([Link](i-1)==[Link](j-1)) dp[i][j]+=dp[i-1][j-1];
}
return (int)dp[m][n];
}

41. Edit Distance

Recursion
int minDist(int i, int j, String s1, String s2) {
if (i < 0) return j + 1;
if (j < 0) return i + 1;
if ([Link](i) == [Link](j)) return minDist(i-1, j-1, s1, s2);
return 1 + [Link](minDist(i-1, j, s1, s2),
[Link](minDist(i, j-1, s1, s2), minDist(i-1, j-1, s1, s2)));
}

Memoization
int dp(int i, int j, String s1, String s2, int[][] memo) {
if (i < 0) return j+1; if (j < 0) return i+1;
if (memo[i][j] != -1) return memo[i][j];
if ([Link](i) == [Link](j)) return memo[i][j] = dp(i-1,j-1,s1,s2,memo);
return memo[i][j] = 1 + [Link](dp(i-1,j,s1,s2,memo),
[Link](dp(i,j-1,s1,s2,memo), dp(i-1,j-1,s1,s2,memo)));
}
Tabulation
int minDistance(String s1, String s2) {
int m=[Link](), n=[Link]();
int[][] dp = new int[m+1][n+1];
for (int i=0;i<=m;i++) dp[i][0]=i;
for (int j=0;j<=n;j++) dp[0][j]=j;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
if ([Link](i-1)==[Link](j-1)) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=1+[Link](dp[i-1][j], [Link](dp[i][j-1],dp[i-1][j-1]));
return dp[m][n];
}

42. Wildcard Matching

Memoization
boolean dp(int i, int j, String s, String p, Boolean[][] memo) {
if (i < 0 && j < 0) return true;
if (j < 0) return false;
if (i < 0) { for(int k=0;k<=j;k++) if([Link](k)!='*') return false; return true; }
if (memo[i][j] != null) return memo[i][j];
if ([Link](j) == '*') return memo[i][j] = dp(i-1,j,s,p,memo)||dp(i,j-1,s,p,memo);
if ([Link](j)=='?' || [Link](i)==[Link](j)) return memo[i][j]=dp(i-1,j-1,s,p,memo);
return memo[i][j] = false;
}

Tabulation
boolean isMatch(String s, String p) {
int m=[Link](), n=[Link]();
boolean[][] dp = new boolean[m+1][n+1]; dp[0][0]=true;
for (int j=1;j<=n;j++) dp[0][j] = dp[0][j-1] && [Link](j-1)=='*';
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
if ([Link](j-1)=='*') dp[i][j]=dp[i-1][j]||dp[i][j-1];
else if ([Link](j-1)=='?'||[Link](i-1)==[Link](j-1)) dp[i][j]=dp[i-1][j-1];
return dp[m][n];
}

43. Longest Palindromic Substring

Tabulation (Expand Around Center)
String longestPalindrome(String s) {
int n=[Link](), start=0, maxLen=1;
boolean[][] dp = new boolean[n][n];
for (int i=0;i<n;i++) dp[i][i]=true;
for (int len=2;len<=n;len++)
for (int i=0;i<=n-len;i++) {
int j=i+len-1;
if (len==2) dp[i][j]=([Link](i)==[Link](j));
else dp[i][j]=([Link](i)==[Link](j) && dp[i+1][j-1]);
if (dp[i][j] && len>maxLen) { maxLen=len; start=i; }
}
return [Link](start, start+maxLen);
}

■ MCM — Matrix Chain Multiplication & Partition DP

44. Matrix Chain Multiplication

Recursion
int mcm(int i, int j, int[] arr) {
if (i >= j) return 0;
int best = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = arr[i-1]*arr[k]*arr[j] + mcm(i,k,arr) + mcm(k+1,j,arr);
best = [Link](best, cost);
}
return best;
}

Memoization
int dp(int i, int j, int[] arr, int[][] memo) {
if (i >= j) return 0;
if (memo[i][j] != -1) return memo[i][j];
int best = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = arr[i-1]*arr[k]*arr[j] + dp(i,k,arr,memo) + dp(k+1,j,arr,memo);
best = [Link](best, cost);
}
return memo[i][j] = best;
}

Tabulation
int mcm(int[] arr) {
int n = [Link] - 1;
int[][] dp = new int[n+1][n+1];
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n-len+1; i++) {
int j = i+len-1; dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = arr[i-1]*arr[k]*arr[j]+dp[i][k]+dp[k+1][j];
dp[i][j] = [Link](dp[i][j], cost);
}
}
return dp[1][n];
}

45. Minimum Cost to Cut the Stick

Memoization
int dp(int i, int j, int[] cuts, int[][] memo) {
if (j - i <= 1) return 0;
if (memo[i][j] != -1) return memo[i][j];
int best = Integer.MAX_VALUE;
for (int k = i+1; k < j; k++)
best = [Link](best, cuts[j]-cuts[i] + dp(i,k,cuts,memo) + dp(k,j,cuts,memo));
return memo[i][j] = best;
}
// Call: add 0 and n to cuts array, sort it

Tabulation
int minCost(int n, int[] cuts) {
int[] c = [Link](cuts, [Link]+2);
c[[Link]]=0; c[[Link]+1]=n;
[Link](c); int m=[Link];
int[][] dp = new int[m][m];
for (int len=2;len<m;len++)
for (int i=0;i<m-len;i++) {
int j=i+len; dp[i][j]=Integer.MAX_VALUE;
for (int k=i+1;k<j;k++)
dp[i][j]=[Link](dp[i][j], c[j]-c[i]+dp[i][k]+dp[k][j]);
}
return dp[0][m-1];
}
46. Burst Balloons
Memoization
int dp(int i, int j, int[] nums, int[][] memo) {
if (i > j) return 0;
if (memo[i][j] != -1) return memo[i][j];
int best = 0;
for (int k = i; k <= j; k++) {
int coins = nums[i-1]*nums[k]*nums[j+1] + dp(i,k-1,nums,memo) + dp(k+1,j,nums,memo);
best = [Link](best, coins);
}
return memo[i][j] = best;
}
// Pad nums with 1 at both ends before calling dp(1, n, nums, memo)

Tabulation
int maxCoins(int[] balloons) {
int n = [Link];
int[] nums = new int[n+2]; nums[0]=nums[n+1]=1;
for (int i=0;i<n;i++) nums[i+1]=balloons[i];
int[][] dp = new int[n+2][n+2];
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]=[Link](dp[i][j], nums[i-1]*nums[k]*nums[j+1]
+(k>i?dp[i][k-1]:0)+(k<j?dp[k+1][j]:0));
}
return dp[1][n];
}

47. Palindrome Partitioning II (Min Cuts)

Memoization
boolean isPalin(int i, int j, String s) {
while (i < j) { if ([Link](i++) != [Link](j--)) return false; } return true;
}
int dp(int i, String s, int[] memo) {
if (i == [Link]()) return 0;
if (memo[i] != -1) return memo[i];
int best = Integer.MAX_VALUE;
for (int j = i; j < [Link](); j++)
if (isPalin(i, j, s)) best = [Link](best, 1 + dp(j+1, s, memo));
return memo[i] = best;
}

Tabulation
int minCut(String s) {
int n = [Link]();
boolean[][] palin = new boolean[n][n];
for (int i=n-1;i>=0;i--)
for (int j=i;j<n;j++)
palin[i][j]=([Link](i)==[Link](j)) && (j-i<=2||palin[i+1][j-1]);
int[] dp = new int[n+1];
for (int i=n-1;i>=0;i--) {
dp[i]=n;
for (int j=i;j<n;j++)
if (palin[i][j]) dp[i]=[Link](dp[i], 1+dp[j+1]);
}
return dp[0]-1;
}
All 47 problems from the TUF+ DSA Checklist DP sheet are covered above in Java. Space-optimised O(n)
variants can be derived from tabulation by keeping only 1-2 rows.