Counting-ways DP

Overview

Counting DPs sum contributions from valid smaller states rather than maximising over them. Two representatives: decode ways counts how many ways a digit string maps back to letters (1='A' … 26='Z'), and Catalan numbers count balanced structures such as valid bracket sequences and distinct binary search trees. The recurring theme is that the guards are the algorithm — a transition contributes only when it is legal, and the classic bugs here are all about admitting an invalid transition (a leading zero, a two-digit code above 26) rather than about the arithmetic.

Why it matters

Counting questions are everywhere: how many valid parses does this input have, how many distinct trees of this size exist, how many ways can this message be interpreted. Ambiguity counts also matter practically — a decoder that finds more than one valid interpretation has found a specification problem. And counting answers grow explosively, which makes them a reliable teacher of overflow discipline.

Core concepts

Sum over valid predecessors. dp[i] = sum of dp[prev] for each legal transition into state i. Contrast with optimisation DPs, which take a max or min instead.

Decode ways. For position i: if s[i-1] != '0', the single digit is valid, so add dp[i-1]. If the two-digit number s[i-2..i-1] lies in 10..26, add dp[i-2]. Both guards are mandatory.

Zero is the trap. '0' has no letter of its own; it is only legal as the second digit of 10 or 20. A string starting with '0' has zero decodings, and "100" is 1 while "1000" is 0.

Base case. dp[0] = 1 — the empty prefix has exactly one (empty) decoding. This seed is what makes the two-digit transition work at i = 2.

Catalan recurrence. C[n] = sum over i of C[i] * C[n-1-i], splitting on the position of the root (or the matching bracket). C[0] = 1. It counts binary search trees, balanced bracket strings, triangulations and more.

Growth. Catalan numbers explode — C[35] already exceeds 64 bits. Use long long and know the limit, or apply the problem's modulus.

Rolling variables. Decode ways needs only the previous two counts, so it runs in O(1) space.

Syntax notes

#include <stdlib.h>
#include <string.h>

/* number of ways to decode a digit string (1='A' .. 26='Z') */
long long decode(const char *s) {
    int n = (int)strlen(s);
    if (n == 0 || s[0] == '0') return 0;      /* leading zero decodes to nothing */
    long long p2 = 1, p1 = 1;                 /* dp[0] = 1, dp[1] = 1 */
    for (int i = 2; i <= n; i++) {
        long long cur = 0;
        if (s[i-1] != '0') cur += p1;                       /* single digit 1..9 */
        int two = (s[i-2] - '0') * 10 + (s[i-1] - '0');
        if (two >= 10 && two <= 26) cur += p2;              /* valid pair 10..26 */
        p2 = p1; p1 = cur;
    }
    return p1;
}

long long catalan(int n) {
    long long *c = calloc((size_t)n + 1, sizeof *c);
    if (!c) return -1;
    c[0] = 1;
    for (int i = 1; i <= n; i++) {
        long long s = 0;
        for (int j = 0; j < i; j++) s += c[j] * c[i-1-j];   /* split on the root */
        c[i] = s;
    }
    long long r = c[n];
    free(c);
    return r;
}

Key points:

• Both guards in decode are required; dropping either overcounts.
• two >= 10 also rejects "05"-style pairs, which are not valid codes.
• long long throughout — these counts grow fast.

Lesson

Some DPs count configurations. Decode ways counts how a digit string maps to letters (with 0-handling), a Fibonacci-shaped recurrence with validity guards. Catalan numbers count balanced parentheses, BST shapes, and triangulations via a convolution recurrence.

Code examples

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static long long decode(const char*s){int n=strlen(s);if(!n||s[0]=='0')return 0;long long p2=1,p1=1;for(int i=2;i<=n;i++){long long cur=0;if(s[i-1]!='0')cur+=p1;int two=(s[i-2]-'0')*10+(s[i-1]-'0');if(two>=10&&two<=26)cur+=p2;p2=p1;p1=cur;}return p1;}
static long long catalan(int n){long long*c=calloc(n+1,sizeof(long long));c[0]=1;for(int i=1;i<=n;i++){long long s=0;for(int j=0;j<i;j++)s+=c[j]*c[i-1-j];c[i]=s;}long long r=c[n];free(c);return r;}
int main(void){
    printf("ways to decode \"226\" (1->A..26->Z) = %lld\n", decode("226"));
    printf("Catalan numbers 0..8:");
    for(int i=0;i<=8;i++) printf(" %lld", catalan(i));
    putchar('\n');
    return 0;
}

Line by line

Common mistakes

Mishandling '0' in decode-ways; off-by-one in the Catalan convolution.

Debugging tips

Compiler errors and warnings:

• -Wchar-subscripts or sign issues when converting digits; s[i] - '0' on a char is fine but validate the character is a digit.
• Silent overflow if the counters are int.

Runtime symptoms:

• "06" returns 1. The leading-zero guard is missing.
• "10" returns 2 instead of 1. You added the single-digit contribution for a '0'; that guard (s[i-1] != '0') is required.
• "27" returns 2 instead of 1. The pair bound is wrong — it must be <= 26.
• "100" wrong. Expect 1; the middle '0' blocks the single-digit path and 00 is not a valid pair.
• Catalan goes negative around n=35. 64-bit overflow — that is the representable limit, not a bug in your recurrence.
• Non-digit input. Behaviour is undefined unless you validate; a stray letter produces nonsense arithmetic.

Technique: test "12" (2), "226" (3), "06" (0), "10" (1), "100" (1). Those five pin down every guard.

Memory safety

• Validate the input alphabet. s[i] - '0' assumes digits; a non-digit silently yields a wild two value. Check with isdigit((unsigned char)s[i]) — and note the unsigned char cast, since passing a negative char to isdigit is undefined.
• Empty string. s[0] is read before the loop, so the n == 0 guard must come first.
• Index bounds. The loop starts at i = 2 so s[i-2] is never negative; starting at 1 would read before the buffer.
• Catalan allocation. Validate n >= 0 before (size_t)n + 1, and check calloc.
• Overflow is the dominant hazard. Counting DPs overflow silently and signed overflow is undefined behaviour. Use long long, apply the problem's modulus when given, and document the largest supported input.
• Free on all paths.

Real-world uses

Concrete uses: Decode-ways is the counting core of ambiguity detection in encodings and simple parsers — if a message has more than one valid decoding, the format is ambiguous. Catalan numbers count valid bracket sequences (compiler and JSON parsing), distinct binary search tree shapes (used in reasoning about tree balance), polygon triangulations, and stack-sortable permutations.

Professional best practices:

Beginner:

• Write the guards down as explicit conditions before coding the sum.
• Test the zero cases first; they are where every bug lives.

Intermediate:

• Use rolling variables when only the last two states matter — decode-ways needs no array at all.
• Apply the modulus from the start when the problem specifies one, rather than overflowing and patching later.
• Validate the input character set at the boundary; counting code is usually fed untrusted strings.

Practice tasks

1. (Beginner) Decode ways. Implement long long decode(const char *s) with both guards. Example: "226" -> 3; "06" -> 0; "10" -> 1. Concepts: valid-transition guards, dp[0] = 1.

2. (Beginner) Catalan numbers. Implement long long catalan(int n). Example: C[3] -> 5; C[5] -> 42. Concepts: split-on-root recurrence.

3. (Intermediate) O(1)-space decode. Confirm your decode uses only two rolling counters and re-verify against the five test strings. Concepts: space reduction.

4. (Intermediate) Balanced brackets. Use the Catalan recurrence to count valid bracket sequences of length 2n, and cross-check by brute-force enumeration for n <= 5. Concepts: validating a formula against an oracle.

Summary

Counting DPs sum over legal predecessors, so the guards are the algorithm. Decode-ways adds the one-digit path only when the digit is not '0' and the two-digit path only when the pair is in 10..26, seeded by dp[0] = 1 for the empty prefix — and every classic bug here is an admitted invalid transition, which is why the zero cases are the tests that matter. Catalan numbers split on the root position and multiply the two sides. Both grow explosively: use long long, apply a modulus when the problem gives one, and validate that the input is actually digits before doing arithmetic on it.

Practice with these exercises

• Decode ways
• Catalan numbers