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.

[解题思路]

本题一开始没有思路，上网搜索后发现与上楼梯那题类似

使用动态规划来解决问题，使用动态规划的目的是降低问题维度，通过解决子问题来来求解原问题

在求解子问题的过程中通过memoization来避免计算重复子问题，不过由于需要存储子问题的解，因而会有额外的空间消耗

令f(n)表示长度为n的输入解码方法，则有如下状态迁移方程：

f(n) = f(n-1) + f(n-2); //s[n] is valid encoding char && s[n-1][n] is valid encoding char

f(n) = f(n-1); //s[n] is valid encoding char while s[n-1][n] is not valid encoding char

f(n) = f(n-2); //s[n] is not valid encoding char && s[n-1][n] is valid encoding char

f(n) = 0; //s[n] is not valid encoding char && s[n-1][n] is not valid encoding char

 1 private static int generate(String s) {
 2         int len = s.length();
 3         if (0 == len || s.charAt(0) == '0') {
 4             return 0;
 5         }
 6         int[] dp = new int[len + 1];
 7         dp[0] = 1;
 8         dp[1] = 1;
 9         for (int i = 2; i < len + 1; i++) {
10             char curChar = s.charAt(i - 1);
11             int curNum = curChar - '0';
12             // s[i] is not valid
13             if (curNum == 0) {
14                 String twoNum = s.substring(i - 2, i);
15                 // s[i-1][i] is valid
16                 if (Integer.parseInt(twoNum) <= 26
17                         && Integer.parseInt(twoNum) >= 10) {
18                     dp[i] = dp[i - 2];
19                 } else {
20                     dp[i] = 0;
21                 }
22             }
23             // s[i] is valid
24             else {
25                 String twoNum = s.substring(i - 2, i);
26                 // s[i-1][i] is valid
27                 if (Integer.parseInt(twoNum) <= 26
28                         && Integer.parseInt(twoNum) >= 10) {
29                     dp[i] = dp[i - 1] + dp[i - 2];
30                 } else {
31                     dp[i] = dp[i - 1];
32                 }
33             }
34         }
35 
36         return dp[len];
37     }