# LeetCode Decode Ways: Dynamic Programming

## Overview

LeetCode Decode Ways: Dynamic Programming is used to solve decode ways problem in iterative manner, this is a modified version of finding fibonacci numbers.

## LeetCode Decode Ways

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:

```'A' -> 1
'B' -> 2
...
'Z' -> 26```

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message `"12"`, it could be decoded as `"AB"` (1 2) or `"L"` (12).

The number of ways decoding `"12"` is 2.

## Solution and Precautions: Dynamic Programming

This could be solved by DP. Let F(n) denote the number of decode ways for a string of length n. The following is the recursive formula:

F(n) = F(n-1) + F(n-2)     if s[n] is a valid encoding digit and s[n-1]s[n] is also a valid encoding number.

F(n) = F(n-1)                     if s[n] is a valid encoding digit and s[n-1]s[n] is NOT a valid encoding number.

F(n) = F(n-2)                     if s[n] is NOT a valid encoding digit and s[n-1]s[n] is  a valid encoding number.

F(n) = 0                             if s[n] is NOT a valid encoding digit and s[n-1]s[n] is NOT  a valid encoding number.

The following Java code is accepted by the LeetCode OJ to pass this Decode Ways problem:

```class Solution {

public int numDecodings(String s) {

int n = s.length();
if (n <= 0)
return 0;
if (1 == n)
return s.charAt(0) <= '9' && s.charAt(0) >= '1' ? 1 : 0;

int a, b, c;
int tmp;
a = b = c = 0;
if (s.charAt(0) <= '9' && s.charAt(0) >= '1')
c = a = b = 1;

for (int i = 1; i < n; ++i) {
a = 0;
if (s.charAt(i) <= '9' && s.charAt(i) >= '1')
a += b;

tmp = Integer.parseInt(s.substring(i-1, i+1));
if (tmp >= 10 && tmp <= 26)
a += c;

c = b;
b = a;
}
return a;
}
}
```

Remarks:

1. The above solution is exactly the same as for solving fibnacci number but in a bit different version by conditioning whether or not to include the value of dp[i-1] or dp[i-2], while for real fibnacci number, these two values are always used to get the next number
2. 01 would not be considered as a valid encoding, so we need to test tmp against 10 and 26 rather than 1 and 26.

## Summary

LeetCode Decode Ways: Dynamic Programming is used to solve decode ways problem in iterative manner, this is a modified version of finding fibonacci numbers.

Written on May 9, 2013