Pattern Reference
Carry DP
"Digit DP where carry propagates through positions. Count numbers with sum of digits equal, etc."
Loading...
Deep Dive Tutorial
Carry DP processes arithmetic column by column. State: carry value (typically 0 or 1 for binary, 0..9 for decimal). Transition: for each column, sum of column digits + incoming carry = column result + 10 × outgoing carry. Count valid digit assignments or verify feasibility. Digit sum DP is a special case: digits must satisfy a target sum, optionally with the tight constraint from digit DP.
Carry DP template for digit addition
// Count ways to assign k-digit values to n variables so their sum = target
// Each variable's digit can be 0-9 in each position
// Process position by position (from LSB), tracking carry
function countValidAssignments(n, target, numDigits) {
// dp[carry] = number of ways to achieve this carry after processing current digit position
let dp = new Map([[0, 1]]); // initial state: carry = 0
// Process each digit position
for (let pos = 0; pos < numDigits; pos++) {
const targetDigit = Math.floor(target / Math.pow(10, pos)) % 10;
const newDp = new Map();
for (const [carry, ways] of dp) {
// Try all possible sums for this column (0 to 9*n)
// The n variables each contribute one digit
for (let colSum = 0; colSum <= 9 * n; colSum++) {
const total = colSum + carry;
const outDigit = total % 10;
const newCarry = Math.floor(total / 10);
if (outDigit === targetDigit) {
// Count assignments giving colSum in n variables
const assignments = countDigitCombinations(n, colSum, 0, 9);
newDp.set(newCarry, (newDp.get(newCarry) || 0) + ways * assignments);
}
}
}
dp = newDp;
}
return dp.get(0) || 0; // must finish with carry = 0
}Worked Problems
hash
Carry DP key insight: Arithmetic on digits works column by column. State = carry value from previous column. For addition of n numbers, carry ≤ n (for decimal: 0..n).
Digit sum DP: More general — count numbers with specific digit sum, sum within range, etc. State = (position, current_sum, tight_bound, leading_zero).
Common patterns:
- Column verification: does a digit assignment satisfy arithmetic constraint?
- Count valid n-tuples: n variables summing to target in each column
- Number reconstruction: build number digit by digit satisfying constraints
Digit sum DP: More general — count numbers with specific digit sum, sum within range, etc. State = (position, current_sum, tight_bound, leading_zero).
Common patterns:
- Column verification: does a digit assignment satisfy arithmetic constraint?
- Count valid n-tuples: n variables summing to target in each column
- Number reconstruction: build number digit by digit satisfying constraints