leetbook_ioa/docs/LCR 165. 解密数字.md
根据题意，可按照下图的思路，总结出 “递推公式” （即转移方程）。
下图中的
num对应本题的ciphertext。
{:align=center width=600}
因此，此题可用动态规划解决，以下按照流程解题。
记数字 $ciphertext$ 第 $i$ 位数字为 $x_i$ ，数字 $ciphertext$ 的位数为 $n$ ； 例如： $ciphertext = 12258$ 的 $n = 5$ , $x_1 = 1$ 。
状态定义： 设动态规划列表 $dp$ ，$dp[i]$ 代表以 $x_i$ 为结尾的数字的翻译方案数量。
转移方程： 若 $x_i$ 和 $x_{i-1}$ 组成的两位数字可被整体翻译，则 $dp[i] = dp[i - 1] + dp[i - 2]$ ，否则 $dp[i] = dp[i - 1]$ 。
$$ dp[i] = \begin{cases} dp[i - 1] + dp[i - 2] & {, (10 x_{i-1} + x_i) \in [10,25]} \ dp[i - 1] & {, (10 x_{i-1} + x_i) \in [0, 10) \cup (25, 99]} \end{cases} $$
可被整体翻译的两位数区间分析： 当 $x_{i-1} = 0$ 时，组成的两位数无法被整体翻译（例如 $00, 01, 02, \cdots$ ），大于 $25$ 的两位数也无法被整体翻译（例如 $26, 27, \cdots$ ），因此区间为 $[10, 25]$ 。
初始状态： $dp[0] = dp[1] = 1$ ，即 “无数字” 和 “第 $1$ 位数字” 的翻译方法数量均为 $1$ ；
返回值： $dp[n]$ ，即此数字的翻译方案数量；
Q： 无数字情况 $dp[0] = 1$ 从何而来？ A： 当 $ciphertext$ 第 $1, 2$ 位的组成的数字 $\in [10,25]$ 时，显然应有 $2$ 种翻译方法，即 $dp[2] = dp[1] + dp[0] = 2$ ，而显然 $dp[1] = 1$ ，因此推出 $dp[0] = 1$ 。
<,,,,,>
class Solution:
def crackNumber(self, ciphertext: int) -> int:
s = str(ciphertext)
a = b = 1
for i in range(2, len(s) + 1):
tmp = s[i - 2:i]
c = a + b if "10" <= tmp <= "25" else a
b = a
a = c
return a
class Solution {
public int crackNumber(int ciphertext) {
String s = String.valueOf(ciphertext);
int a = 1, b = 1;
for(int i = 2; i <= s.length(); i++) {
String tmp = s.substring(i - 2, i);
int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
}
class Solution {
public:
int crackNumber(int ciphertext) {
string s = to_string(ciphertext);
int a = 1, b = 1, len = s.size();
for(int i = 2; i <= len; i++) {
string tmp = s.substr(i - 2, 2);
int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
};
此题的动态规划计算是 对称的 ，即 从左向右 遍历（从第 $dp[2]$ 计算至 $dp[n]$ ）和 从右向左 遍历（从第 $dp[n - 2]$ 计算至 $dp[0]$ ）所得方案数一致。从右向左遍历的代码如下所示。
class Solution:
def crackNumber(self, ciphertext: int) -> int:
s = str(ciphertext)
a = b = 1
for i in range(len(s) - 2, -1, -1):
a, b = (a + b if "10" <= s[i:i + 2] <= "25" else a), a
return a
class Solution {
public int crackNumber(int ciphertext) {
String s = String.valueOf(ciphertext);
int a = 1, b = 1;
for(int i = s.length() - 2; i > -1; i--) {
String tmp = s.substring(i, i + 2);
int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
}
class Solution {
public:
int crackNumber(int ciphertext) {
string s = to_string(ciphertext);
int a = 1, b = 1, len = s.size();
for(int i = len - 2; i > -1; i--) {
string tmp = s.substr(i, 2);
int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
b = a;
a = c;
}
return a;
}
};
上述方法虽然已经节省了 $dp$ 列表的空间占用，但字符串 $s$ 仍使用了 $O(N)$ 大小的额外空间。
<,,,,,,,,,,,,,>
class Solution:
def crackNumber(self, ciphertext: int) -> int:
a = b = 1
y = ciphertext % 10
while ciphertext > 9:
ciphertext //= 10
x = ciphertext % 10
tmp = 10 * x + y
c = a + b if 10 <= tmp <= 25 else a
a, b = c, a
y = x
return a
class Solution {
public int crackNumber(int ciphertext) {
int a = 1, b = 1, x, y = ciphertext % 10;
while(ciphertext > 9) {
ciphertext /= 10;
x = ciphertext % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
}
class Solution {
public:
int crackNumber(int ciphertext) {
int a = 1, b = 1, x, y = ciphertext % 10;
while(ciphertext > 9) {
ciphertext /= 10;
x = ciphertext % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
};