# 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**:

- 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
- 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.