Where to Find Dynamic Programming Solutions in TheAlgorithms/Java: Complete Package Guide

All dynamic programming solutions in TheAlgorithms/Java are organized under the com.thealgorithms.dynamicprogramming package in src/main/java/com/thealgorithms/dynamicprogramming/, featuring over 20 algorithmic implementations from classic knapsack problems to advanced string matching and graph DP.

TheAlgorithms/Java is a widely-used open-source repository containing production-quality algorithm implementations. For developers searching for dynamic programming solutions in TheAlgorithms/Java, the codebase offers a systematic collection located in a dedicated package structure. Each class provides self-contained solutions with comprehensive Javadoc, exposing static methods that demonstrate both top-down memoization and bottom-up tabulation techniques.

Package Structure and File Locations

The primary directory for dynamic programming solutions is:

src/main/java/com/thealgorithms/dynamicprogramming/

This package contains individual Java classes for each algorithm, following the package declaration com.thealgorithms.dynamicprogramming. Additionally, certain graph-based dynamic programming algorithms reside in related packages:

• src/main/java/com/thealgorithms/graph/ - Contains TravelingSalesman.java implementing the Held-Karp algorithm
• src/main/java/com/thealgorithms/datastructures/graphs/ - Contains FloydWarshall.java for all-pairs shortest path DP

Core Dynamic Programming Implementations

The repository covers major DP paradigms through specific classes with well-documented method signatures:

Optimization and Knapsack Problems:

• In KnapsackZeroOneTabulation.java, the knapsack(int[] values, int[] weights, int capacity) method implements the bottom-up tabulation approach.
• In KnapsackZeroOne.java, the knapsackMemo(int[], int[], int) method provides the memoization alternative.
• In MatrixChainMultiplication.java, use matrixChainOrder(int[]) to compute optimal parenthesization.
• In WineProblem.java, choose between maxProfitTopDown(int[]) and maxProfitBottomUp(int[]) for profit maximization strategies.

String and Sequence Algorithms:

• In LongestCommonSubsequence.java, call lcs(String, String) for the classic LCS solution.
• In LevenshteinDistance.java, invoke computeDistance(String, String) with space-optimized variants available.
• In RegexMatching.java, compare isMatchMemo(String, String) and isMatchDP(String, String) to see memoization versus tabulation.
• In PalindromicPartitioning.java, use minCut(String) to determine the minimum cuts needed for palindrome partitioning.
• In UniqueSubsequencesCount.java, the countUniqueSubsequences(String, String) method counts distinct subsequences.

Grid, Path, and Combinatorial Problems:

• In UniquePaths.java, access both uniquePathsDP(int m, int n) (2-D array) and uniquePathsDP1D(int m, int n) (space-optimized 1-D array).
• In ClimbingStairs.java, the climbStairsDP(int) method solves the Fibonacci-style stair climbing problem.
• In CatalanNumber.java, calculate combinatorial results via catalanDP(int).
• In AssignmentUsingBitmask.java, solve assignment problems using assign(int[][]).

Advanced DP Patterns:

• In LongestIncreasingSubsequenceNLogN.java, the lengthOfLIS(int[]) method implements the efficient N log N solution.
• In SubsetSumSpaceOptimized.java, check partition feasibility with canPartition(int[]) using O(sum) space complexity.
• In NeedlemanWunsch.java, perform bioinformatics alignment via globalAlignment(String, String).
• In TravelingSalesman.java (graph package), solve TSP using heldKarpTSP(int[][]).
• In FloydWarshall.java (datastructures/graphs package), compute all-pairs shortest paths with floydWarshall(int[][]).

Practical Code Examples

Grid Unique Paths Calculation

import com.thealgorithms.dynamicprogramming.UniquePaths;

public class DemoUniquePaths {
    public static void main(String[] args) {
        int m = 3, n = 7;
        long paths2D = UniquePaths.uniquePathsDP(m, n);
        long paths1D = UniquePaths.uniquePathsDP1D(m, n);
        System.out.println("2-D DP: " + paths2D);
        System.out.println("1-D DP: " + paths1D);
    }
}

Source: UniquePaths.java in src/main/java/com/thealgorithms/dynamicprogramming/UniquePaths.java.

0/1 Knapsack Problem

import com.thealgorithms.dynamicprogramming.KnapsackZeroOneTabulation;

public class DemoKnapsack {
    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        int maxProfit = KnapsackZeroOneTabulation.knapsack(values, weights, capacity);
        System.out.println("Maximum profit = " + maxProfit);
    }
}

Source: KnapsackZeroOneTabulation.knapsack in src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulation.java.

Palindromic Partitioning Minimum Cuts

import com.thealgorithms.dynamicprogramming.PalindromicPartitioning;

public class DemoPalPartition {
    public static void main(String[] args) {
        String s = "abcbm";
        int minCuts = PalindromicPartitioning.minCut(s);
        System.out.println("Minimum cuts needed = " + minCuts);
    }
}

Source: PalindromicPartitioning.minCut in src/main/java/com/thealgorithms/dynamicprogramming/PalindromicPartitioning.java.

Traveling Salesman Problem (Held-Karp)

import com.thealgorithms.graph.TravelingSalesman;

public class DemoTSP {
    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };
        int optimalCost = TravelingSalesman.heldKarpTSP(dist);
        System.out.println("Optimal TSP cost = " + optimalCost);
    }
}

Source: TravelingSalesman.heldKarpTSP in src/main/java/com/thealgorithms/graph/TravelingSalesman.java.

Summary

• Primary Location: All core dynamic programming solutions reside in src/main/java/com/thealgorithms/dynamicprogramming/ under the package com.thealgorithms.dynamicprogramming.
• Architecture: Each class is self-contained with static utility methods, comprehensive Javadoc, and often includes both memoization and tabulation variants.
• Graph Exceptions: Specialized DP algorithms like Floyd-Warshall and Traveling Salesman are located in src/main/java/com/thealgorithms/datastructures/graphs/ and src/main/java/com/thealgorithms/graph/ respectively.
• Usage Pattern: Import the specific class and invoke the static method directly without instantiation; all methods accept primitive arrays or Strings and return results directly.

Frequently Asked Questions

What is the exact package path for dynamic programming solutions in TheAlgorithms/Java?

The standard dynamic programming implementations are located in the package com.thealgorithms.dynamicprogramming, physically stored at src/main/java/com/thealgorithms/dynamicprogramming/. However, some specialized algorithms like TravelingSalesman (Held-Karp algorithm) and FloydWarshall are located in the graph-related packages under com.thealgorithms.graph and com.thealgorithms.datastructures.graphs respectively.

Do the DP classes in TheAlgorithms/Java include both memoization and tabulation approaches?

Many classes provide both approaches according to the TheAlgorithms/Java source code. For example, WineProblem.java exposes maxProfitTopDown(int[]) for memoization and maxProfitBottomUp(int[]) for tabulation. Similarly, RegexMatching.java offers isMatchMemo(String, String) and isMatchDP(String, String) to demonstrate both techniques, allowing you to compare time-space trade-offs directly.

How do I run the dynamic programming solutions in my own Java project?

Clone the repository and import the specific class from the com.thealgorithms.dynamicprogramming package (or the relevant graph package for TSP and Floyd-Warshall). Each algorithm exposes public static methods that accept primitive arrays or Strings and return results immediately. For instance, call LongestCommonSubsequence.lcs(text1, text2) or KnapsackZeroOneTabulation.knapsack(values, weights, capacity) without instantiating the class.

Are there space-optimized implementations available?

Yes, several algorithms include space-optimized variants as implemented in the repository. UniquePaths.java provides both uniquePathsDP() (2-D array) and uniquePathsDP1D() (1-D array). SubsetSumSpaceOptimized.java implements canPartition(int[]) using O(sum) space instead of O(n×sum), and LevenshteinDistance.java includes optimized versions that reduce memory from O(n×m) to O(min(n,m)).

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}