Dynamic Programming in Java

Dynamic programming is a powerful concept used in the field of computer science and data structures. It is an algorithmic technique used to solve complex problems by breaking them down into smaller subproblems. Dynamic programming is used to solve problems that have overlapping subproblems, which means that the same subproblems can be used multiple times in the same problem. This technique is useful for optimizing problems and reducing the amount of time and memory needed to solve them. It is also used to find the most efficient solution to a problem. In this article, we will discuss what dynamic programming is, how it works in Java, and how to use it to solve data structure and algorithms problems.

What is Dynamic Programming?

Dynamic programming is an algorithmic technique used to solve complex problems by breaking them down into smaller subproblems. It is used to solve problems that have overlapping subproblems, which means that the same subproblems can be used multiple times in the same problem. Dynamic programming is used to optimize problems and reduce the amount of time and memory needed to solve them. It is also used to find the most efficient solution to a problem.

Dynamic programming is a type of bottom-up approach, which means that it starts with the smallest possible subproblem and builds up the solution to the overall problem by solving the small subproblems. This is different from a top-down approach, which starts with the overall problem and works down to the individual subproblems.

Dynamic programming works by storing the solutions to the subproblems in a table. This table is known as a memoization table. The memoization table is used to store the solutions of the subproblems so that they can be used again in the future. This helps to reduce the amount of time and memory needed to solve the problem.

Dynamic Programming in Java

Dynamic programming can be used to solve many different types of problems in Java. It is most commonly used to solve problems related to data structures and algorithms. In order to use dynamic programming in Java, you must first understand the concept of memoization.

Memoization is a technique used in dynamic programming that stores the solutions of the subproblems in a table. This table is known as a memoization table. The memoization table is used to store the solutions of the subproblems so that they can be used again in the future. This helps to reduce the amount of time and memory needed to solve the problem.

In Java, the memoization table is implemented using a two-dimensional array. The first dimension of the array is used to store the subproblem, and the second dimension is used to store the solution. The array is initialized with all zeros. The first dimension of the array is then populated with the subproblems and the second dimension is populated with the solutions.

The following example demonstrates how to use dynamic programming in Java to solve the Fibonacci sequence problem. The Fibonacci sequence is a sequence of consecutive numbers where each number is the sum of the two preceding numbers.

// Fibonacci sequence using dynamic programming in Java
public class Fibonacci {
 
    // Memoization table
    private static int[][] memo = new int[100][2];
 
    // Fibonacci function
    public static int fib(int n) {
        if (memo[n][0] == 0) {
            if (n <= 1) {
                memo[n][0] = n;
            }
            else {
                memo[n][0] = fib(n - 1) + fib(n - 2);
            }
        }
        return memo[n][0];
    }
 
    public static void main(String[] args) {
        // Print the first 10 Fibonacci numbers
        for (int i = 0; i < 10; i++) {
            System.out.println(fib(i));
        }
    }
}

In this example, we have used dynamic programming to solve the Fibonacci sequence problem. We have used a two-dimensional array to store the solutions of the subproblems in a memoization table. This helps to reduce the amount of time and memory needed to solve the problem.

Using Dynamic Programming to Solve Data Structures and Algorithms Problems

Dynamic programming can be used to optimize many different types of data structures and algorithms problems. It is particularly useful for problems that have overlapping subproblems. By storing the solutions of the subproblems in a memoization table, it is possible to reduce the amount of time and memory needed to solve the problem.

One example of how dynamic programming can be used to solve data structures and algorithms problems is the knapsack problem. The knapsack problem is a classic problem in computer science and is a type of optimization problem. The goal of the problem is to select a subset of items from a given set of items such that the total weight of the selected items does not exceed a given weight limit and the total value of the selected items is maximized.

// Knapsack problem using dynamic programming in Java
public class Knapsack {
 
    // Memoization table
    private static int[][] memo = new int[100][100];
 
    // Knapsack function
    public static int knapsack(int[] weights, int[] values, int capacity) {
        if (memo[weights.length][capacity] == 0) {
            if (weights.length == 0 || capacity == 0) {
                memo[weights.length][capacity] = 0;
            }
            else {
                int maxValue = 0;
                int maxWeight = 0;
 
                for (int i = 0; i < weights.length; i++) {
                    int weight = weights[i];
                    int value = values[i];
 
                    if (weight <= capacity) {
                        int currentValue = value + knapsack(weights, values, capacity - weight);
                        maxValue = Math.max(maxValue, currentValue);
                        maxWeight = Math.max(maxWeight, weight);
                    }
                }
 
                memo[weights.length][capacity] = maxValue;
            }
        }
        return memo[weights.length][capacity];
    }
 
    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 4, 5};
        int[] values = {5, 10, 20, 30, 40};
        int capacity = 10;
 
        System.out.println(knapsack(weights, values, capacity));
    }
}

In this example, we have used dynamic programming to solve the knapsack problem. We have used a two-dimensional array to store the solutions of the subproblems in a memoization table. This helps to reduce the amount of time and memory needed to solve the problem.

Conclusion

Dynamic programming is a powerful concept used in the field of computer science and data structures. It is an algorithmic technique used to solve complex problems by breaking them down into smaller subproblems. Dynamic programming is used to optimize problems and reduce the amount of time and memory needed to solve them. It is also used to find the most efficient solution to a problem.

In Java, dynamic programming is implemented using a two-dimensional array. This array is known as a memoization table and is used to store the solutions of the subproblems so that they can be used again in the future. This helps to reduce the amount of time and memory needed to solve the problem.

Dynamic programming can be used to solve many different types of problems related to data structures and algorithms. It is particularly useful for problems that have overlapping subproblems. By storing the solutions of the subproblems in a memoization table, it is possible to reduce the amount of time and memory needed to solve the problem.

Exercises

public class MaxSubArray { 
  
    // Memoization table 
    private static int[][] memo = new int[100][100]; 
  
    // Function to find the maximum sum of a subarray 
    public static int maxSubArray(int[] arr, int n) 
    { 
        if (memo[n][n] == 0) { 
            int maxSum = Integer.MIN_VALUE; 
  
            // Consider all subarrays and calculate 
            // their sum 
            for (int i = 0; i < n; i++) { 
                int sum = 0; 
  
                // Calculate sum of subarray arr[i..j] 
                for (int j = i; j < n; j++) { 
                    sum += arr[j]; 
  
                    // Update maximum sum if required 
                    maxSum = Math.max(maxSum, sum); 
                } 
            } 
  
            // Store the maximum sum in the memoization table 
            memo[n][n] = maxSum; 
        } 
  
        // Return the maximum sum from the memoization table 
        return memo[n][n]; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
        int n = arr.length; 
        System.out.println(maxSubArray(arr, n)); 
    } 
} 

public class LCS { 
    // Memoization table 
    private static int[][] memo = new int[100][100]; 
  
    // Function to find the length of the longest common subsequence 
    public static int lcs(char[] X, char[] Y, int m, int n) 
    { 
        if (memo[m][n] == 0) { 
            if (m == 0 || n == 0) { 
                memo[m][n] = 0; 
            } 
            else if (X[m - 1] == Y[n - 1]) { 
                memo[m][n] = 1 + lcs(X, Y, m - 1, n - 1); 
            } 
            else { 
                memo[m][n] = Math.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n)); 
            } 
        } 
        return memo[m][n]; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        String s1 = "ABCDGH"; 
        String s2 = "AEDFHR"; 
  
        char[] X = s1.toCharArray(); 
        char[] Y = s2.toCharArray(); 
        int m = X.length; 
        int n = Y.length; 
  
        System.out.println("Length of LCS is" + " " + lcs(X, Y, m, n)); 
    } 
} 

public class MinCoins { 
  
    // Memoization table 
    private static int[][] memo = new int[100][100]; 
  
    // Function to find the minimum number of coins 
    public static int minCoins(int[] coins, int amount) 
    { 
        if (memo[coins.length][amount] == 0) { 
            if (amount == 0) { 
                memo[coins.length][amount] = 0; 
            } 
            else { 
                int min = Integer.MAX_VALUE; 
  
                // Try every coin that has smaller value than amount 
                for (int i = 0; i < coins.length; i++) { 
                    if (coins[i] <= amount) { 
                        int val = minCoins(coins, amount - coins[i]); 
  
                        // Check for INT_MAX to avoid overflow and see if 
                        // result can minimized 
                        if (val != Integer.MAX_VALUE && val + 1 < min) { 
                            min = val + 1; 
                        } 
                    } 
                } 
  
                // Store the minimum number of coins in the memoization table 
                memo[coins.length][amount] = min; 
            } 
        } 
        return memo[coins.length][amount]; 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        int[] coins = { 1, 2, 5, 10 }; 
        int amount = 17; 
  
        System.out.println("Minimum coins required is " + minCoins(coins, amount)); 
    } 
}

public class LongestIncreasingSubsequence { 
	public static int findLIS(int[] arr) { 
		int[] lis = new int[arr.length]; 
		int max = 0; 

		for (int i = 0; i < arr.length; i++) { 
			lis[i] = 1; 
			for (int j = 0; j < i; j++) { 
				if (arr[i] > arr[j] && lis[i] < lis[j] + 1) { 
					lis[i] = lis[j] + 1; 
				} 
			} 
			max = Math.max(max, lis[i]); 
		} 

		return max; 
	} 

	public static void main(String[] args) { 
		int[] arr = {10, 22, 9, 33, 21, 50, 41, 60}; 
		System.out.println(findLIS(arr)); 
	} 
} 

public class LongestPalindromicSubsequence { 
	public static int findLPS(String str) { 
		int n = str.length(); 
		int[][] dp = new int[n][n]; 
		
		for (int i = 0; i < n; i++) { 
			dp[i][i] = 1; 
		} 

		for (int l = 2; l <= n; l++) { 
			for (int i = 0; i < n - l + 1; i++) { 
				int j = i + l - 1; 
				if (l == 2 && str.charAt(i) == str.charAt(j)) { 
					dp[i][j] = 2; 
				} else if (str.charAt(i) == str.charAt(j)) { 
					dp[i][j] = dp[i + 1][j - 1] + 2; 
				} else { 
					dp[i][j] = Math.max(dp[i + 1][j], 
									dp[i][j - 1]); 
				} 
			} 
		} 
		return dp[0][n - 1]; 
	} 

	public static void main(String[] args) { 
		String str = "agbdba"; 
		System.out.println(findLPS(str)); 
	} 
}