【Python】动态规划之数字转化字符串

规定A对应1，B对应2... Z对应26
举个栗子： 111就可以转化为 'AAA', 'KA', 'AK'
给定一个只有数字字符组成的str，返回一共有多少种转化结果

暴力递归思路：

• 可以把这个字符串想成0 ~ N-1位，当在第index位的时候，只考虑N-index的方法，相加即为index位的方法。f(n) = f(n-1) + f(n-2)

• 确定递归出口，

  • 当index到达末尾，即无其他方法，计为 1

  • 当index位置上为“0”时，即方案错误，无法转化，计为0

    （index可以看做头，以"0"为首部的数字没办法转化）

• 确定递推式

  • 单转：直接index+1
  • 双转：确定index+1不越界，且，这两位数小于27
  • 单转 + 双转，即为所有的可能

DP思路：

• 构建dp，由于字符串转化数是根据index位置决定的，线性的，只需要构建一维数组，为什么是N+1，因为当index走到最后（越界）时，只有一种转化方法，dp[N] = 1
• 判断依赖关系：index依赖于index+1的方法，所以从后往前填充dp
• 填充dp
  • 判断情况，头为"0"时，决策错误，无转化方法
  • 单转：直接加
  • 双转：判断是否符合情况再加（我这样写比较帅，但是多进行了一次赋值操作）
• 返回值：index从0开始

def translate_str(string):
    if not string or len(string) == 0:  # 边界条件
        return 0
    
    def process(string, index):
        # 只考虑index之后的转化，0~index不需要考虑
        if len(string) == index:
            return 1
        if string[index] == "0":  # 之前做的决定有问题
            return 0
        
        # 存在两种情况：单转和双转
        # 单转
        ways = process(string, index+1)
        # 双转，index+1不越界，且，string[index, index+2]小于27
        if index+1 < len(string) and int(string[index:index+2]) < 27:
            ways += process(string, index + 2)
        return ways
    return process(string, 0)


def dp_translate_str(string):
    if not string or len(string) == 0:  # 边界条件
        return 0
    N = len(string)
    dp = [0 for _ in range(N+1)]
    dp[N] = 1
    for i in range(N-1, -1, -1):
        if string[i] == "0":  # 当为0时，决策错误
            continue
        dp[i] = dp[i+1]
        dp[i] += dp[i+2] if i + 1 < N and int(string[i:i+2]) < 27 else 0
        
    return dp[0]






print(translate_str("11111"))  # 8
print(translate_str("12313"))  # 6
print(translate_str("13035643242311"))  # 0，里面有个30，没办法转

print(dp_translate_str("11111"))
print(dp_translate_str("12313"))
print(dp_translate_str("13035643242311"))

题目同：可以自己练习一下

剑指 Offer 46. 把数字翻译成字符串

https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/