這一題我是有思路的，就是動(dòng)態(tài)規(guī)劃，因?yàn)樽蛲砩蟿偤每戳藙?dòng)態(tài)規(guī)劃的算法，理解也差不多，但是有一點(diǎn)沒(méi)搞清楚，就是怎么去寫狀態(tài)轉(zhuǎn)移方程式。這里在粗略復(fù)習(xí)一下動(dòng)態(tài)規(guī)劃的幾個(gè)重要思想：重疊子問(wèn)題，遞歸，緩存，無(wú)后效性，最優(yōu)子結(jié)構(gòu)性質(zhì)
回到這一題上，思路如下：
如果字符串是空的，顯然解碼方式為0
如果首字符為0，那么這個(gè)字符串是無(wú)效字符串，解碼為0
dp[i]表示前面長(zhǎng)度為i的字符串的解碼方式，如果s[i-2]s[i-1] 為 11-19， 21-26那么這兩個(gè)字母有兩種編碼方式，分別占用兩個(gè)字符和一個(gè)字符，如果占用兩個(gè)字符，那么編碼方法數(shù)與dp[i-2]相等，如果占用一個(gè)字符，那么編碼方法數(shù)與dp[i-1]相等，因此，編碼方法數(shù)目 = dp[i-2] +dp[i-1].
如果s[i-2][i-1]為10或者20，那么顯然只有一種編碼方式，占了兩個(gè)字符，因此dp[i]=dp[i-2]
如果s[i-2][i-1]不滿足上述情況，即有可能<10或者>26，那么只看最后一位，只要不是0,都只有一種編碼方式，因此dp[i]=dp[i-1]
若最后一位為0，且前面不為1或者2，顯然是不合法的輸入，return 0

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        if s[0] == '0':
            return 0
        dp = [1,1]
        for i in range(2,len(s)+1):
            if int(s[i-2:i]) > 10 and int(s[i-2:i]) <= 26 and int(s[i-2:i]) != 20:
                dp.append(dp[i-1] + dp[i-2])
            elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
                dp.append(dp[i-2])
            elif int(s[i-1])!= 0:
                dp.append(dp[i-1])
            else:
                return 0
        return dp[-1]