Digit Sum - Implementation

$dp[pos][tight][sum]$ = count of valid completions. Base case: $pos = n$ returns $(sum == S) ? 1 : 0$. Memoize only when $tight = false$. When tight, the valid digit range depends on the specific limit, breaking reuse. Alternative: memoize all states with limit baked in. Use $dp[pos][tight][sum]$ where tight is binary. Trade space for simplicity. Time: $O(n \cdot S \cdot 10)$ where $n$ is digit count. Space: $O(n \cdot S)$ with memoization.

Time complexity: $O(\log N \cdot S)$.

Space complexity: $O(\log N \cdot S)$.