# Dynamic Programming - 91. Decode Ways

91. 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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

go：

``````func numDecodings(s string) int {

if s == "" {return 0}

leng := len(s)
if leng == 0 { return 1 }
dp := make([]int, leng+1)
dp[0] = 1;
if s[0] == '0' {
dp[1] = 0
} else {
dp[1] = 1
}

var prev, next uint8
for i := 2; i <= leng; i++ {
next = s[i-1] - '0'
prev = s[i-2] - '0'

sum := prev * 10 + next

if sum == 0 || next == 0 && prev >= 3 {
return 0
} else if next == 0 {
dp[i] = dp[i-2] // 123 12320
} else if prev != 0 && sum <= 26 { // 123 -> 1 + 12
dp[i] = dp[i-1] + dp[i-2]
} else {
dp[i] = dp [i-1]  // 1234 = 123
}
}

return dp[leng]
}
``````

Nothing just happens, it's all part of a plan.