[FEATURE REQUEST] Add Digit Dynamic Programming Template

[premmsharma122]

What would you like to Propose?

Add a generalized, production-grade template implementation of the Digit Dynamic Programming (Digit DP) technique along with a complete unit test suite under the dynamicprogramming package.

Issue details

Description

Digit Dynamic Programming (Digit DP) is an advanced algorithmic technique used to efficiently count or evaluate numbers within a range $[L, R]$ that satisfy specific digit-based constraints.

Instead of an iterative brute force lookup, the approach evaluates numbers digit-by-digit from left to right (most significant to least significant) using a compressed search tree with memoization. This template tracks three critical architectural dimensions:

1. Index (Position): The specific digit placement currently being evaluated.
2. Accumulated Property State: The specific criteria tracking array (e.g., sum of digits, digit frequencies, parity matching).
3. Tight Flag Matrix Constraint: A binary state (1 or 0) specifying whether the current prefixes are bounded by the maximum prefix of the upper range parameter limit or are completely free to iterate from 0 to 9.

Adding a clean, reusable boilerplate/template for Digit DP in the dynamicprogramming section will serve as a foundational study layout for students looking to learn state-transition constraints, state-compression arrays, branch pruning optimizations, and range query adjustments.

Architectural Path Locations

To maintain symmetry with the existing project layout, the addition will be introduced at:

• Core Logic: src/main/java/com/thealgorithms/dynamicprogramming/DigitDP.java
• Unit Testing Suite: src/test/java/com/thealgorithms/dynamicprogramming/DigitDPTest.java

Time & Space Complexity

• Time Complexity: $O(\text{Number of Digits} \times \text{State Array Size} \times 10)$ — Processing a $10^{18}$ boundary ceiling executes instantly within a fraction of a millisecond.
• Space Complexity: $O(\text{Number of Digits} \times \text{State Array Size} \times 2)$ — Bounded by the static allocation bounds of the memoization table grid.

Quality Standards Compliance Plan

The implementation will explicitly comply with the repository's build requirements:

1. Zero Instantiation Overheads: The class will follow utility design criteria (final class implementation with an explicit private zero-argument constructor to block accidental instantiations).
2. Standardization Validation: Employs standard JUnit 5 assertion suites targeting descriptive edge configurations (e.g., zero boundaries, negative values, large maximum long capacities, and completely missing permutations).
3. Checkstyle Compliance: Variables, constants, and matrix definitions are completely isolated without loose magic constants or check violations.

Comprehensive Mock Execution Trace

Problem Parameters:

• Range: $[1, 100]$
• Constraint Filter: Exact sum of digits must equal 5.

Expected Calculation Yield:

• Output Quantifier: 6
• Valid Value Set: 5, 14, 23, 32, 41, 50

Additional Information

This feature bridges a major gap between standard dynamic programming problems (like knapsack or longest common subsequence) and digit state-compression techniques. It provides a generalized structure that developers and learners can study to understand advanced combinatorial enumeration and branch-pruning methods.