View SubsetSum.java
/*
Problem: Given an array of integers and sum S,
find whether the subset exists to create sum S or not.
*/
import java.util.ArrayList;
import java.util.List;
public class SubsetSum {
// complexity: time O(n*m), space O(n*m), n: number of integers, m: sum
static boolean canMakeSubset(int[] ary, int sum) {
View LinearParition.java
/*
Problem: Given an array of integers and number of workers,
find a fair amount of partitions.
(sum of each partition may or may not be the same)
This is a k-partition problem, also known as a fair workload problem.
*/
public class LinearPartition {
static int INF = Integer.MAX_VALUE;
// complexity: O(n*k), space O(n*k)
View EditDistance.java
/*
Problem: Given two strings, find the edit distance to make those the same.
edit - insert, remove, replace
*/
public class EditDistance
// complexity: time O(3^n), space O(n)
static int findEditDistanceRecur(String X, String Y, int m, int n) {
// base case
if (m == 0) { // insert rest of all
return n;
View Knapsack.java
/*
Problem: Given values and corresponding weights,
find a maximum profit.
Optimal substructure:
- item i is included
- item i is excluded
*/
public class Knapsack {
// complexity: time: O(2^n), space O(n)
View RodCutting.java
/*
Problem: Given a rod's length and prices of each length,
find a maximum profit.
*/
public class RodCutting {
// complexity: time O(2^(n-1)), space O(n)
static int cutRodRecur(int[] price, int l) {
// base case
if (l <= 0) {
View LongestPalindromicSubsequence.java
/*
Problem: Given a string, find the longest palindromic subsequence.
Maintains right upper half of the table.
*/
public class LongestPalindromicSubsequence {
// complexity: time O(n^2), space O(n^2)
static int findLPS(String S) {
int n = S.length();
int[][] memo = new int[n][n];
View LongestPalindromicSubstring.java
/*
Given a string, find the longest palindromic substring.
Maintains right upper half of the table.
*/
public class LongestPalindromicSubstring {
// complexity: time O(n^2), space O(n^2)
static int findLPS(String S) {
int n = S.length();
boolean[][] memo = new boolean[n][n];
View LongestCommonSubsequence.java
/*
Problem: Given two strings, find the longest common subsequence.
Optimal substructure:
LCS(X, Y, m, n) = LCS(X, Y, m-1, n-1) + 1 if X[m-1] == Y[n-1]
MAX(LCS(X, Y, m-2, n-1), LCS(X, Y, m-1, n-2)) otherwise
*/
public class LongestCommonSubsequence {
// complexity: time O(2^n), space O(n)
static int findLCSRecur(String X, String Y, int m, int n) {
View LongestCommonSubstring.java
/*
Problem: Given two strings, find the longest common substring.
Optimal substructure:
LCS(X, Y, m, n) = LCS(X, Y, m-1, n-1) + 1 if X[m-1] == Y[n-1]
0 otherwise
*/
public class LongestCommonSubstring {
// complexity: time O(n*m), space O(n*m)