# Dynamic Programming Solution for the Decode Ways Problem: A Complete Guide

> Learn the dynamic programming solution for the Decode Ways problem. Efficiently count valid letter interpretations of numeric strings in O(n) time using tabulation and a clear guide.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**The dynamic programming solution for the Decode Ways problem uses bottom-up tabulation to count valid alphabetic interpretations of a numeric string in O(n) time by tracking whether each single digit (1-9) or double-digit pair (10-26) forms a valid letter mapping.**

The Decode Ways problem is a classic interview question that tests your ability to recognize overlapping subproblems and optimal substructure—hallmarks of dynamic programming. In the `kdn251/interviews` repository, you'll find a clean Java implementation that demonstrates exactly how to solve this LeetCode challenge using a systematic DP approach. This guide breaks down the dynamic programming solution for the Decode Ways problem, explaining the recurrence relation, base cases, and space optimizations used in the reference implementation.

## Understanding the Decode Ways Problem

The problem asks you to determine the total number of ways to decode a numeric string where 'A' maps to 1, 'B' to 2, and 'Z' to 26. A valid decoding must parse the entire string without leading zeros—meaning '0' cannot stand alone, and two-digit numbers must fall within the 10-26 range to correspond to letters.

## Dynamic Programming Approach and Recurrence Relation

The solution leverages the fact that the number of ways to decode a string starting at position `i` depends only on the solutions for positions `i+1` and `i+2`. This creates a natural bottom-up dynamic programming structure.

### Defining the DP State

Let `dp[i]` represent the number of ways to decode the substring `s[i:]`, which is the suffix of the string starting at index `i`. The final answer we seek is `dp[0]`, representing the number of ways to decode the entire string from the beginning.

### Base Cases

The dynamic programming solution for the Decode Ways problem requires two base cases to terminate the recurrence:

- `dp[n] = 1`: An empty suffix (when we've processed the entire string) has exactly one valid decoding—the empty string itself.
- `dp[n-1] = 1` if the last character is not `'0'`, otherwise `0`: A single non-zero digit always maps to one letter, but `'0'` cannot stand alone.

### Transition Logic

For each position `i` from `n-2` down to `0`, apply the following rules as implemented in `kdn251/interviews`:

1. If `s[i] == '0'`, set `dp[i] = 0` because `'0'` cannot start a valid encoding.
2. Otherwise, start with `dp[i] = dp[i+1]` (decoding the current digit as a single letter).
3. If the two-digit number formed by `s[i]` and `s[i+1]` is between 10 and 26, add `dp[i+2]` to account for decoding these two digits as a single letter.

The formal recurrence is:

```

if s[i] == '0':
    dp[i] = 0
else:
    dp[i] = dp[i+1] + (10 <= value(s[i..i+1]) <= 26 ? dp[i+2] : 0)

```

## Java Implementation from kdn251/interviews

The reference implementation in the `kdn251/interviews` repository follows exactly this dynamic programming approach. The `numDecodings` method in [`leetcode/string/DecodeWays.java`](https://github.com/kdn251/interviews/blob/main/leetcode/string/DecodeWays.java) and [`company/uber/DecodeWays.java`](https://github.com/kdn251/interviews/blob/main/company/uber/DecodeWays.java) implements the bottom-up solution with O(n) space:

```java
public class DecodeWays {
    public int numDecodings(String s) {
        int n = s.length();

        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n + 1];
        dp[n] = 1;                                   // empty suffix
        dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0; // last character

        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                continue;                            // dp[i] stays 0
            } else {
                int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                dp[i] = (twoDigit <= 26) ? dp[i + 1] + dp[i + 2] : dp[i + 1];
            }
        }

        return dp[0];
    }
}

```

This implementation correctly handles edge cases such as leading zeros and invalid two-digit combinations while computing the total decode ways in a single reverse pass through the string.

## Space Optimization to O(1)

As noted in the source analysis, the dynamic programming solution for the Decode Ways problem only requires the previous two states (`dp[i+1]` and `dp[i+2]`) to compute the current value. This allows reducing the space complexity from O(n) to O(1) by using two variables instead of an array:

```java
public int numDecodingsOptimized(String s) {
    int n = s.length();
    if (n == 0) return 0;

    int a = 1; // dp[i+2]
    int b = s.charAt(n - 1) != '0' ? 1 : 0; // dp[i+1]

    for (int i = n - 2; i >= 0; i--) {
        int cur = 0;
        if (s.charAt(i) != '0') {
            cur = b;
            int two = Integer.parseInt(s.substring(i, i + 2));
            if (two <= 26) cur += a;
        }
        a = b;
        b = cur;
    }
    return b;
}

```

This optimized version maintains the same O(n) time complexity while using constant auxiliary space, making it ideal for memory-constrained environments or very large input strings.

## Time and Space Complexity Analysis

The dynamic programming solution for the Decode Ways problem implemented in `kdn251/interviews` achieves optimal complexity bounds:

- **Time Complexity:** O(n), where n is the length of the input string. The algorithm performs a single reverse iteration through the string, performing O(1) work (character checks and integer parsing) at each position.
- **Space Complexity:** O(n) for the standard implementation using the `dp` array, or O(1) for the space-optimized variant that tracks only the last two states.

Both implementations handle all edge cases specified in the problem statement, including strings starting with '0', consecutive zeros, and invalid two-digit combinations greater than 26.

## Summary

- The **dynamic programming solution for the Decode Ways problem** treats each position in the string as a subproblem depending only on the next one or two positions.
- The recurrence relation checks if the current digit (1-9) and potential two-digit number (10-26) form valid letter mappings, summing the ways from `dp[i+1]` and `dp[i+2]`.
- The `kdn251/interviews` repository implements this in [`leetcode/string/DecodeWays.java`](https://github.com/kdn251/interviews/blob/main/leetcode/string/DecodeWays.java) and [`company/uber/DecodeWays.java`](https://github.com/kdn251/interviews/blob/main/company/uber/DecodeWays.java) using a bottom-up approach with O(n) time complexity.
- Space optimization reduces memory usage from O(n) to O(1) by maintaining only the previous two DP states.

## Frequently Asked Questions

### What is the base case for the Decode Ways dynamic programming solution?

The base cases occur at the end of the string. `dp[n]` (empty suffix) equals 1 because there is exactly one way to decode an empty string. `dp[n-1]` equals 1 if the last character is not '0' (mapping to a single letter), or 0 if it is '0' (invalid standalone digit). These base cases terminate the recurrence and allow the backward iteration to compute valid results for earlier positions.

### Why does the dynamic programming solution iterate backwards through the string?

The algorithm iterates backwards (from `n-2` down to `0`) because the number of ways to decode the suffix starting at position `i` depends on the already-computed values for positions `i+1` and `i+2`. This bottom-up approach ensures that subproblems are solved before they are needed by larger problems, avoiding the overhead of recursive calls and memoization while guaranteeing that `dp[i+1]` and `dp[i+2]` contain valid counts when computing `dp[i]`.

### How does the solution handle invalid inputs like "0" or "30"?

The solution handles '0' characters by checking if `s[i] == '0'` at each position. If true, `dp[i]` remains 0 because '0' cannot start a valid encoding. For two-digit numbers like "30", the algorithm checks if the value is ≤ 26; since 30 > 26, it does not add `dp[i+2]`, effectively treating the '0' as invalid in that context and returning 0 ways for that path.

### Can the Decode Ways dynamic programming solution be implemented recursively with memoization?

Yes, the dynamic programming solution can be implemented recursively using memoization (top-down DP). The recursive function would check the same conditions (single digit 1-9, double digit 10-26) and cache results for each index `i` to avoid recomputing subproblems. However, the bottom-up iterative approach shown in `kdn251/interviews` is generally preferred for its O(1) space optimization potential and avoidance of recursion stack overhead, which could cause stack overflow on very long strings.