題目
給定一個數(shù)字牍蜂，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” 漾根，1 翻譯成 “b”，……鲫竞，11 翻譯成 “l(fā)”辐怕，……，25 翻譯成 “z”从绘。一個數(shù)字可能有多個翻譯寄疏。請編程實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法僵井。
示例 1:
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯陕截，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)批什，非商業(yè)轉(zhuǎn)載請注明出處农曲。
思路
普通的動態(tài)規(guī)劃，每新加入一個字符驻债，都可以考慮兩種情況：
- 把這個數(shù)字當(dāng)成獨立的數(shù)字乳规；
- 這個數(shù)字和前面一個數(shù)字組合。
當(dāng)這個數(shù)字是獨立的數(shù)字却汉，那就是n-1個數(shù)字的時候驯妄，不過每個樣例后面加一個字符。
當(dāng)這個數(shù)字和前面的組合分為兩種情況合砂，一個是<= 26的時候青扔，這種情況就和n-2個數(shù)字的情況一樣了，如果>26那就沒有了翩伪。
代碼
由于每次計算只需要前兩個數(shù)字微猖，所以不需要數(shù)組。
class Solution:
def translateNum(self, num: int) -> int:
# 最大是25
# 動態(tài)規(guī)劃讀一個字還是讀兩個
# f(i) = f(i-1)+f(i-2) 如果num[i-1:i+1]<26 else f(i-1)
# dp = [0]*len(num)
num = [int(i) for i in str(num)]
dp0 = 1
dp1 = 1
for i in range(1,len(num)):
if 9 < 10*num[i-1]+num[i] <26 :
dp1 = dp0 + dp1
dp0 = dp1 - dp0
else:
dp0,dp1 = dp1,dp1
return dp1
