Leetcode Link: 剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）
题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
从暴力递归到动态规划
暴力递归
我的问题
我总是纠结于如果当前 idx 位置的东西我不用，那么我是不是应该向 process 中传入两个参数 idx0 和 idx1， 表示没用的起始位置和结束位置（就是当前位置） 然而，正确的做法是，如果能够确定的划分出子问题的分解形式，就直接将子问题分解，不要弄有的没的，就跟爬楼梯一样。
本题是从左往右的尝试模型
子问题是考虑 idx 到结尾的数字，能够转化成字符串的种数
实际上，当前位置的转化情况只有下面几种：
- 当前位置单独转化（后面需要idx+1）
- 当前位置和下一个位置一起转化 (后面需要 idx+2)
一起转化需要保证下面三个前提：
- 第一位（idx 位）不为 0
- 两位组成的数字不能超过字母对应的数字的范围
- 第二位不能超过数字长度
class Solution:
def translateNum(self, num: int) -> int:
return self.process(str(num), 0)
def process(self, num, idx):
# base case 能走到末尾，说明之前的转化是可以的，因此转化数为1，是之前做的决定
if idx == len(num):
return 1
# 情况1：idx位置自己转
p1 = self.process(num, idx+1)
# 情况2：idx和下一位一起转，不一定存在需要判断
p2 = 0
if num[idx]!='0' and idx+1 < len(num) and int(num[idx:idx+2])<26:
p2 = self.process(num, idx+2)
return p1 + p2 …暴力竟然能通过？
动态规划
只依赖于 idx，是一个一维表
class Solution:
def translateNum(self, num: int) -> int:
num = str(num)
dp = [0 for _ in range(len(num)+1)]
dp[len(num)] = 1
# 这里是从右向左填写的，开始就写错了
# 一定要分析位置依赖确定遍历方向！
for idx in range(len(num)-1,-1,-1):
dp[idx] = dp[idx+1]
if num[idx]!='0' and idx+1 < len(num) and int(num[idx:idx+2])<26:
dp[idx] += dp[idx+2]
return dp[0]启发和联系
从左往右的尝试模型，好像是当前位置不断后移（后移的步数不一定是1，可能是更大的步数，需要根据子问题的分解情况），不考虑当前位置之前的东西，只返回从当前位置到末尾的答案（一般就是问题的答案）