Dynamic Programming Examples in Java
Dynamic Programming (DP) is a technique used to solve complex problems by breaking
them into simpler overlapping subproblems and storing their results to avoid recomputation.
1. Fibonacci Sequence (DP Approach)
public class FibonacciDP {
static int fib(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) {
[Link](fib(10)); // Output: 55
}
}
Explanation: Avoids multiple recursion by storing results in an array.
2. Factorial Using DP (Tabulation)
public class FactorialDP {
static long factorial(int n) {
long[] dp = new long[n+1];
dp[0] = 1;
for(int i=1; i<=n; i++) {
dp[i] = i * dp[i-1];
}
return dp[n];
}
public static void main(String[] args) {
[Link](factorial(5)); // Output: 120
}
}
Explanation: Bottom-up approach avoids repeated multiplications.
3. Coin Change Problem
public class CoinChange {
static int countWays(int[] coins, int n, int sum) {
int[] dp = new int[sum+1];
dp[0] = 1;
for(int coin : coins) {
for(int i=coin; i<=sum; i++) {
dp[i] += dp[i-coin];
}
}
return dp[sum];
}
public static void main(String[] args) {
int[] coins = {1, 2, 3};
[Link](countWays(coins, [Link], 4)); // Output: 4
}
}
Explanation: Uses 1D DP to calculate number of ways to make a sum.
4. Longest Common Subsequence (LCS)
public class LCS {
static int lcs(String X, String Y) {
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] = dp[i-1][j-1] + 1;
else
dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
public static void main(String[] args) {
[Link](lcs("AGGTAB", "GXTXAYB")); // Output: 4
}
}
Explanation: Classic 2D DP problem for sequence comparison.
5. Knapsack Problem (0/1 Knapsack)
public class Knapsack {
static int knapSack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n+1][W+1];
for(int i=1;i<=n;i++){
for(int w=1;w<=W;w++){
if(wt[i-1] <= w)
dp[i][w] = [Link](val[i-1] + dp[i-1][w-wt[i-1]], dp[i-
1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] val = {60, 100, 120};
int[] wt = {10, 20, 30};
int W = 50;
[Link](knapSack(W, wt, val, [Link])); // Output: 220
}
}
Explanation: Maximizes value under weight constraint using 2D DP.
6. Minimum Cost Path in Grid
public class MinCostPath {
static int minCost(int[][] cost, int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = cost[0][0];
for(int i=1;i<m;i++) dp[i][0] = dp[i-1][0]+cost[i][0];
for(int j=1;j<n;j++) dp[0][j] = dp[0][j-1]+cost[0][j];
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j] = cost[i][j] + [Link](dp[i-1][j],
[Link](dp[i][j-1], dp[i-1][j-1]));
return dp[m-1][n-1];
}
public static void main(String[] args) {
int[][] cost = {{1,2,3},{4,8,2},{1,5,3}};
[Link](minCost(cost,3,3)); // Output: 8
}
}
Explanation: Finds minimal cost from top-left to bottom-right cell.
7. Edit Distance (Levenshtein Distance)
public class EditDistance {
static int editDist(String str1, String str2) {
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-1], [Link](dp[i-1][j],
dp[i][j-1]));
}
}
return dp[m][n];
}
public static void main(String[] args) {
[Link](editDist("kitten","sitting")); // Output: 3
}
}
Explanation: Classic string transformation problem using 2D DP.
8. Maximum Subarray Sum (Kadane’s Algorithm)
public class MaxSubarray {
static int maxSubArray(int[] arr) {
int maxSoFar=arr[0], maxEnding=arr[0];
for(int i=1;i<[Link];i++){
maxEnding = [Link](arr[i], maxEnding+arr[i]);
maxSoFar = [Link](maxSoFar,maxEnding);
}
return maxSoFar;
}
public static void main(String[] args) {
int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
[Link](maxSubArray(arr)); // Output: 6
}
}
Explanation: Optimized 1D DP to find maximum sum of contiguous subarray.
9. Rod Cutting Problem
public class RodCutting {
static int cutRod(int[] price, int n) {
int[] dp = new int[n+1];
for(int i=1;i<=n;i++){
int maxVal=0;
for(int j=0;j<i;j++)
maxVal = [Link](maxVal, price[j]+dp[i-j-1]);
dp[i]=maxVal;
}
return dp[n];
}
public static void main(String[] args) {
int[] price = {1,5,8,9,10,17,17,20};
int n = 8;
[Link](cutRod(price,n)); // Output: 22
}
}
Explanation: Maximizes revenue by cutting rod into optimal lengths.
10. Counting Unique Binary Search Trees (Catalan
Number)
public class UniqueBST {
static int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i]=0;
for(int j=1;j<=i;j++)
dp[i]+=dp[j-1]*dp[i-j];
}
return dp[n];
}
public static void main(String[] args) {
[Link](numTrees(3)); // Output: 5
}
}
Explanation: DP counts number of unique BSTs using Catalan numbers.
✅ Key Observations
• 1D DP: Fibonacci, max subarray, rod cutting
• 2D DP: LCS, edit distance, knapsack, min cost path
• DP reduces time complexity exponentially in recursive solutions to polynomial time.
• Can often convert recursive memoization into iterative tabulation.