> 文档中心 > LeetCode91-解码方法,dp>记忆化搜索

LeetCode91-解码方法,dp>记忆化搜索


题目链接:LeetCode91


题意

        给定一个有数字组成的字符串,要求计算出有多少种解码方法来解释该数字字符串。

        其中,映射规则是

 

思路一,动态规划

        对于一个合理的搜索,不难得出,dp[i]=dp[i-1]*c1+dp[i-2]*c2

        条件c1s[i]∈['1','9'],条件c2s[i-2:i]属于["10","26"],(因为对于两位字符的映射,第一位不能为'0')。

代码(Golang+DP)

func numDecodings(s string) int {    dp:=make([]int,len(s)+1)    dp[0]=1    for i:=1;i1 && digit(s[i-2:i]){     dp[i]+=dp[i-2] }    }    return dp[len(s)]}func digit(s string)bool{    if len(s)==2 && s[0]=='0'{ return false    }    now,_:=strconv.Atoi(s)    if now0{ return true    }    return false}

思路二,记忆化搜索

        可以非常直观的想到用深度优先搜索,搜索思路如下:

  1. 若当前字符合理,则进入下一步搜索,即搜索id+1,
  2. 若当前字符和下一个字符组成的两位数符合要求,则进入下一步搜索,即搜索id+2
  3. 结束条件:当id==len(s),则表示我们找到了一个有效的匹配串,ans++

缺点:

        对于一个数字串,会出现很多次重复搜索,比如“11112”,对于“1,1”“11”两种情况,都要重新搜索一下“112”,当字符串长度非常大的时候,这样的重复搜索会导致超时。

改进:

        记忆化搜索,在回溯过程中,为了避免重复搜索,可以把搜索过的值保存下来,比如对于“11112”后缀“112”,答案为3,那么就可以保存下来,这样在搜索完“11”的时候,就可以直接将“112”的搜索结果加到答案中。

代码,(Golang+Memorize Search)

func numDecodings(s string) int {    mp:=make(map[int]int)    var dfs func(i int)int    dfs=func(i int)int{ if i==len(s){     return 1 } if mp[i]>0{     return mp[i] } res:=0 if digit(s[i:i+1]){     res+=dfs(i+1) } if i<len(s)-1 && digit(s[i:i+2]){     res+=dfs(i+2) } mp[i]=res return res    }    return dfs(0)}func digit(s string)bool{    if len(s)==2 && s[0]=='0'{ return false    }    now,_:=strconv.Atoi(s)    if now0{ return true    }    return false}