6 Dynamic Programming problems for your next coding interview

Image for post
Image for post

0–1 Knapsack Problem

Image for post
Image for post

The problem

The simple solution

public class Knapsack {
public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}

private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex < 0 || currentIndex >= profits.length) return 0;

// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn’t process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity — weights[currentIndex], currentIndex + 1);

// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);
return Math.max(profit1, profit2);
}

public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println(maxProfit);
}
}

One DP approach: Top-down with memoization

public class Knapsack {

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
Integer[][] dp = new Integer[profits.length][capacity + 1];
return this.knapsackRecursive(dp, profits, weights, capacity, 0);
}

private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity, int currentIndex) {

// base checks
if (capacity <= 0 || currentIndex < 0 || currentIndex >= profits.length)
return 0;

// if we have already processed similar problem, return the result from
memory
if(dp[currentIndex][capacity] != null)
return dp[currentIndex][capacity];

// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we
shouldn’t process this
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights, capacity — weights[currentIndex], currentIndex + 1);

// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(dp, profits, weights, capacity,
currentIndex + 1);

dp[currentIndex][capacity] = Math.max(profit1, profit2);
return dp[currentIndex][capacity];
}

public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {1, 6, 10, 16};
int[] weights = {1, 2, 3, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 7);
System.out.println(maxProfit);
}
}

Unbounded knapsack problem

Image for post
Image for post

The problem

The brute force solution

public class Knapsack {

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
return this.knapsackRecursive(profits, weights, capacity, 0);
}

private int knapsackRecursive(int[] profits, int[] weights, int capacity,
int currentIndex) {
// base checks
if (capacity <= 0 || profits.length == 0 || weights.length != profits.length ||
currentIndex < 0 || currentIndex >= profits.length)
return 0;

// recursive call after choosing the items at the currentIndex, note that we recursive call on all
// items as we did not increment currentIndex
int profit1 = 0;
if( weights[currentIndex] <= capacity )
profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
capacity — weights[currentIndex], currentIndex);

// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

return Math.max(profit1, profit2);
}

public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {15, 50, 60, 90};
int[] weights = {1, 3, 4, 5};
int maxProfit = ks.solveKnapsack(profits, weights, 8);
System.out.println(maxProfit);
}
}

One DP solution: Bottom-up programming

public class Knapsack {

public int solveKnapsack(int[] profits, int[] weights, int capacity) {
// base checks
if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
return 0;

int n = profits.length;
int[][] dp = new int[n][capacity + 1];

// populate the capacity=0 columns
for(int i=0; i < n; i++)
dp[i][0] = 0;

// process all sub-arrays for all capacities
for(int i=0; i < n; i++) {
for(int c=1; c <= capacity; c++) {
int profit1=0, profit2=0;
if(weights[i] <= c)
profit1 = profits[i] + dp[i][c-weights[i]];
if( i > 0 )
profit2 = dp[i-1][c];
dp[i][c] = profit1 > profit2 ? profit1 : profit2;
}
}

// maximum profit will be in the bottom-right corner.
return dp[n-1][capacity];
}

public static void main(String[] args) {
Knapsack ks = new Knapsack();
int[] profits = {15, 50, 60, 90};
int[] weights = {1, 3, 4, 5};
System.out.println(ks.solveKnapsack(profits, weights, 8));
System.out.println(ks.solveKnapsack(profits, weights, 6));
}
}

Longest palindromic subsequence

Image for post
Image for post

The problem

The simple solution

public class LPS {

public int findLPSLength(String st) {
return findLPSLengthRecursive(st, 0, st.length()-1);
}

private int findLPSLengthRecursive(String st, int startIndex, int endIndex) {
if(startIndex > endIndex)
return 0;

// every sequence with one element is a palindrome of length 1
if(startIndex == endIndex)
return 1;

// case 1: elements at the beginning and the end are the same
if(st.charAt(startIndex) == st.charAt(endIndex))
return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1);

// case 2: skip one element either from the beginning or the end
int c1 = findLPSLengthRecursive(st, startIndex+1, endIndex);
int c2 = findLPSLengthRecursive(st, startIndex, endIndex-1);
return Math.max(c1, c2);
}

public static void main(String[] args) {
LPS lps = new LPS();
System.out.println(lps.findLPSLength(“abdbca”));
System.out.println(lps.findLPSLength(“cddpd”));
System.out.println(lps.findLPSLength(“pqr”));
}
}

One DP approach: Top-down with memoization

public class LPS {

public int findLPSLength(String st) {
Integer[][] dp = new Integer[st.length()][st.length()];
return findLPSLengthRecursive(dp, st, 0, st.length()-1);
}

private int findLPSLengthRecursive(Integer[][] dp, String st, int startIndex, int endIndex) {
if(startIndex > endIndex)
return 0;

// every sequence with one element is a palindrome of length 1
if(startIndex == endIndex)
return 1;

if(dp[startIndex][endIndex] == null) {
// case 1: elements at the beginning and the end are the same
if(st.charAt(startIndex) == st.charAt(endIndex)) {
dp[startIndex][endIndex] = 2 + findLPSLengthRecursive(dp, st, startIndex+1, endIndex-1);
} else {
// case 2: skip one element either from the beginning or the end
int c1 = findLPSLengthRecursive(dp, st, startIndex+1, endIndex);
int c2 = findLPSLengthRecursive(dp, st, startIndex, endIndex-1);
dp[startIndex][endIndex] = Math.max(c1, c2);
}
}

return dp[startIndex][endIndex];
}

public static void main(String[] args) {
LPS lps = new LPS();
System.out.println(lps.findLPSLength(“abdbca”));
System.out.println(lps.findLPSLength(“cddpd”));
System.out.println(lps.findLPSLength(“pqr”));
}
}

The Fibonacci Problem

Image for post
Image for post

The problem

The basic solution

public class Fibonacci {

public int CalculateFibonacci(int n)
{
if(n < 2)
return n;
return CalculateFibonacci(n-1) + CalculateFibonacci(n-2);
}

public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
}
}

One DP approach: Bottom-up

public class Fibonacci {

public int CalculateFibonacci(int n)
{
int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;

for(int i=2; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2];

return dp[n];
}

public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
System.out.println(fib.CalculateFibonacci(7));
}
}
public class Fibonacci {

public int CalculateFibonacci(int n)
{
if(n < 2)
return n;

int n1=0, n2=1, temp;

for(int i=2; i<=n; i++) {
temp = n1 + n2;
n1 = n2;
n2 = temp;
}

return n2;
}

public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
System.out.println(fib.CalculateFibonacci(5));
System.out.println(fib.CalculateFibonacci(6));
System.out.println(fib.CalculateFibonacci(7));
}
}

Longest Common Substring

Image for post
Image for post

The problem

The simple solution

public class LCS {

public int findLCSLength(String s1, String s2) {
return findLCSLengthRecursive(s1, s2, 0, 0, 0);
}

private int findLCSLengthRecursive(String s1, String s2, int i1, int i2, int count) {
if(i1 == s1.length() || i2 == s2.length())
return count;

if(s1.charAt(i1) == s2.charAt(i2))
count = findLCSLengthRecursive(s1, s2, i1+1, i2+1, count+1);

int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, 0);
int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, 0);

return Math.max(count, Math.max(c1, c2));
}

public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength("abdca", "cbda"));
System.out.println(lcs.findLCSLength("passport", "ppsspt"));
}
}
public class LCS {

public int findLCSLength(String s1, String s2) {
int maxLength = Math.max(s1.length(), s2.length());
Integer[][][] dp = new Integer[s1.length()][s2.length()][maxLength];
return findLCSLengthRecursive(dp, s1, s2, 0, 0, 0);
}

private int findLCSLengthRecursive(Integer[][][] dp, String s1, String s2, int i1, int i2, int count) {
if(i1 == s1.length() || i2 == s2.length())
return count;

if(dp[i1][i2][count] == null) {
int c1 = count;
if(s1.charAt(i1) == s2.charAt(i2))
c1 = findLCSLengthRecursive(dp, s1, s2, i1+1, i2+1, count+1);
int c2 = findLCSLengthRecursive(dp, s1, s2, i1, i2+1, 0);
int c3 = findLCSLengthRecursive(dp, s1, s2, i1+1, i2, 0);
dp[i1][i2][count] = Math.max(c1, Math.max(c2, c3));
}

return dp[i1][i2][count];
}

public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength("abdca", "cbda"));
System.out.println(lcs.findLCSLength("passport", "ppsspt"));
}
}

Longest Common Subsequence

Image for post
Image for post

The problem

The simple solution

public class LCS {

public int findLCSLength(String s1, String s2) {
return findLCSLengthRecursive(s1, s2, 0, 0);
}

private int findLCSLengthRecursive(String s1, String s2, int i1, int i2) {
if(i1 == s1.length() || i2 == s2.length())
return 0;

if(s1.charAt(i1) == s2.charAt(i2))
return 1 + findLCSLengthRecursive(s1, s2, i1+1, i2+1);

int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1);
int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2);

return Math.max(c1, c2);
}

public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength("abdca", "cbda"));
System.out.println(lcs.findLCSLength("passport", "ppsspt"));
}
}

One DP approach: Bottom-up

public class LCS {

public int findLCSLength(String s1, String s2) {
int[][] dp = new int[s1.length()+1][s2.length()+1];
int maxLength = 0;
for(int i=1; i <= s1.length(); i++) {
for(int j=1; j <= s2.length(); j++) {
if(s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

maxLength = Math.max(maxLength, dp[i][j]);
}
}
return maxLength;
}

public static void main(String[] args) {
LCS lcs = new LCS();
System.out.println(lcs.findLCSLength("abdca", "cbda"));
System.out.println(lcs.findLCSLength("passport", "ppsspt"));
}
}

Keep Learning!

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store