資訊專欄INFORMATION COLUMN
摘要：經(jīng)總結(jié)，發(fā)現(xiàn)當(dāng)前字符前面的兩個(gè)字符和一個(gè)字符可以拿出來(lái)進(jìn)行分析。當(dāng)前的數(shù)目可以作為和的數(shù)目的疊加。所以關(guān)系式是其他的特殊情況可以進(jìn)行特殊處理。需要注意的是如果錢(qián)兩位是，，則這兩位作廢，不能計(jì)入其他情況的統(tǒng)計(jì)，即。
描述
A message containing letters from A-Z is being encoded to numbers
using the following mapping:"A" -> 1 "B" -> 2 ... "Z" -> 26 Given an encoded message containing
digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L"
(12).The number of ways decoding "12" is 2.
class Solution:
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
if s[0]=="0" :
return 0
elif len(s)==1:
return 1
length=len(s)
dp=[0 for _ in range(length+1)]
print("dp:==>",dp)
dp[0]=1
dp[1]=1
for i in range(2,length+1):
l2=int(s[i-2:i])
l1=int(s[i-1:i])
if 10",dp)
out=dp[length]
return out
if __name__=="__main__":
st=Solution()
num="2626"
num="0"
num="11"
num="1"
num="0"
num="11"
num="110"
out=st.numDecodings(num)
print(out)
解釋：本地是動(dòng)態(tài)規(guī)劃解決，所以需要分清楚往后疊加增加字符時(shí)的數(shù)目之間的變化規(guī)律。經(jīng)總結(jié)，發(fā)現(xiàn)當(dāng)前字符前面的兩個(gè)字符和一個(gè)字符可以拿出來(lái)進(jìn)行分析。 當(dāng)前的數(shù)目可以作為cur_index-2和cur_index-1的數(shù)目的疊加。只跟前兩個(gè)位置的字符處產(chǎn)生的數(shù)目有關(guān)系。
所以dp關(guān)系式是：dp[n]=dp[n-1]+dp[n-2].其他的特殊情況可以進(jìn)行特殊處理。比如10，20，位數(shù)為1的情況。 需要注意的是：如果錢(qián)兩位是10，20，則這兩位作廢，不能計(jì)入其他情況的統(tǒng)計(jì)，即 dp[i]=dp[i-2]。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/44621.html
摘要：作者碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。機(jī)器人試圖達(dá)到網(wǎng)格的右下角在下圖中標(biāo)記為。問(wèn)總共有多少條不同的路徑例如，上圖是一個(gè)的網(wǎng)格。有多少可能的路徑說(shuō)明和的值均不超過(guò)。示例輸入輸出解釋從左上角開(kāi)始，總共有條路徑可以到達(dá)右下角。 作者: 碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計(jì)者、開(kāi)發(fā)者；負(fù)責(zé)小米應(yīng)用商店、日歷、開(kāi)屏廣告業(yè)務(wù)線研發(fā)；主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)；關(guān)注推薦、搜索、廣...
摘要：作者碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。機(jī)器人試圖達(dá)到網(wǎng)格的右下角在下圖中標(biāo)記為。問(wèn)總共有多少條不同的路徑例如，上圖是一個(gè)的網(wǎng)格。有多少可能的路徑說(shuō)明和的值均不超過(guò)。示例輸入輸出解釋從左上角開(kāi)始，總共有條路徑可以到達(dá)右下角。 作者: 碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計(jì)者、開(kāi)發(fā)者；負(fù)責(zé)小米應(yīng)用商店、日歷、開(kāi)屏廣告業(yè)務(wù)線研發(fā)；主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)；關(guān)注推薦、搜索、廣...
摘要：最新更新請(qǐng)見(jiàn)動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路解碼是有規(guī)律的，所以我們可以嘗試動(dòng)態(tài)規(guī)劃。如果字符串的第位和第位不能組成有效二位數(shù)字，而且第位不是的話，說(shuō)明我們是在第位的解碼方法上繼續(xù)解碼。 Decode Ways 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...
閱讀 3204·2021-10-14 09:42
閱讀 3572·2019-08-26 13:56
閱讀 3482·2019-08-26 11:59
閱讀 948·2019-08-23 18:00
閱讀 2213·2019-08-23 17:51
閱讀 3534·2019-08-23 17:17
閱讀 1487·2019-08-23 15:11
閱讀 5205·2019-08-23 15:05
