WikiGalaxy
Dynamic Programming Applications in Java
Fibonacci Sequence
Understanding Fibonacci with Dynamic Programming
The Fibonacci sequence is a classic example of dynamic programming, where we optimize the recursive approach by storing the results of subproblems.
public class FibonacciDP {
public static int fibonacci(int n) {
if (n <= 1) return n;
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Console Output:
55
0/1 Knapsack Problem
Solving the Knapsack Problem Efficiently
The 0/1 Knapsack problem is solved using dynamic programming by building a table where each entry represents the maximum value that can be achieved with a given weight limit.
public class Knapsack {
public static int knapSack(int W, int[] wt, int[] val, int n) {
int[][] K = new int[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
public static void main(String[] args) {
int[] val = {60, 100, 120};
int[] wt = {10, 20, 30};
int W = 50;
System.out.println(knapSack(W, wt, val, val.length));
}
}
Console Output:
220
Longest Common Subsequence
Finding the Longest Common Subsequence
The Longest Common Subsequence (LCS) problem can be efficiently solved using dynamic programming by constructing a table that stores lengths of LCS for different pairs of indices.
public class LCS {
public static int lcs(String X, String Y) {
int m = X.length();
int n = Y.length();
int[][] L = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X.charAt(i-1) == Y.charAt(j-1))
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
public static void main(String[] args) {
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println(lcs(X, Y));
}
}
Console Output:
4
Coin Change Problem
Minimizing Coins for Change
The Coin Change problem involves finding the minimum number of coins needed to make a certain amount. Dynamic programming helps by building a table of solutions to subproblems.
public class CoinChange {
public static int minCoins(int[] coins, int m, int V) {
int[] table = new int[V + 1];
table[0] = 0;
for (int i = 1; i <= V; i++) table[i] = Integer.MAX_VALUE;
for (int i = 1; i <= V; i++) {
for (int j = 0; j < m; j++) {
if (coins[j] <= i) {
int sub_res = table[i - coins[j]];
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
}
return table[V];
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int V = 11;
System.out.println(minCoins(coins, coins.length, V));
}
}
Console Output:
3
Edit Distance
Calculating Edit Distance Between Strings
The Edit Distance problem calculates the minimum number of operations required to convert one string into another. Dynamic programming builds a table to derive the solution efficiently.
public class EditDistance {
public static int editDist(String str1, String str2, int m, int n) {
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1]));
}
}
return dp[m][n];
}
public static void main(String[] args) {
String str1 = "sunday";
String str2 = "saturday";
System.out.println(editDist(str1, str2, str1.length(), str2.length()));
}
}
Console Output:
3
