46. 把数字翻译成字符串.md

解题思路

动态规划

dp[i] 表示 i 长度的字符串的翻译种数

如果新增字符不能和前面最后一个字符构成新的翻译，那其实相当于也没有新的翻译种数，就是 dp[i] = dp[i-1]

如果新增字符可以和前面最后一个字符构成新的翻译，那相比于上面的，它新增了去掉最后一个字符的情况，即 dp[i] = dp[i-1] + dp[i-2]

func translateNum(num int) int {
    s := strconv.Itoa(num)
    dp := make([]int, len(s)+1)
    dp[0] = 1
    dp[1] = 1
    for i := 2; i <= len(s); i++ {
        v := (s[i-2] - '0') * 10 + (s[i-1] - '0')
        if v >= 10 && v <= 25 {
            dp[i] = dp[i-1] + dp[i-2]
        } else {
            dp[i] = dp[i-1]
        }
    }
    return dp[len(s)]
}