Dynamic Programming: Tabulation (Bottom-Up Approach) in Java

Understanding the tabulation (bottom-up) approach in dynamic programming, and applying it to solve problems like Longest Common Subsequence and Knapsack problem in Java.

⬅ Previous Next ➡

Dynamic Programming with Tabulation in Java: Practice Problems and Solutions

This collection provides practice problems related to dynamic programming and the tabulation approach (bottom-up) in Java. It's designed to encourage active learning and strengthen problem-solving skills for competitive programming.

Practice Problems

Problem 1: Fibonacci Sequence (Tabulation)

Calculate the nth Fibonacci number using the tabulation method.

Java Solution

 public class Fibonacci {
                        public static int fibonacci(int n) {
                            int[] dp = new int[n + 1];
                            dp[0] = 0;
                            if (n > 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) {
                            int n = 10;
                            System.out.println("Fibonacci(" + n + ") = " + fibonacci(n)); // Output: Fibonacci(10) = 55
                        }
                    }

Problem 2: Minimum Cost Path (Tabulation)

Given a 2D grid where each cell has a cost associated with it, find the minimum cost path from the top-left cell to the bottom-right cell. You can only move right or down.

Java Solution

 public class MinCostPath {
                        public static int minCost(int[][] cost) {
                            int m = cost.length;
                            int n = cost[0].length;
                            int[][] dp = new int[m][n];

                            dp[0][0] = cost[0][0];

                            // Initialize first row
                            for (int i = 1; i < n; i++) {
                                dp[0][i] = dp[0][i - 1] + cost[0][i];
                            }

                            // Initialize first column
                            for (int i = 1; i < m; i++) {
                                dp[i][0] = dp[i - 1][0] + cost[i][0];
                            }

                            // Fill the dp table
                            for (int i = 1; i < m; i++) {
                                for (int j = 1; j < n; j++) {
                                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + cost[i][j];
                                }
                            }

                            return dp[m - 1][n - 1];
                        }

                        public static void main(String[] args) {
                            int[][] cost = {
                                {1, 2, 3},
                                {4, 8, 2},
                                {1, 5, 3}
                            };
                            System.out.println("Minimum Cost = " + minCost(cost)); // Output: Minimum Cost = 8
                        }
                    }

⬅ Previous Next ➡