LeetCode91-解码方法，dp＞记忆化搜索

题目链接：LeetCode91

题意

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

        其中，映射规则是

思路一，动态规划

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

        条件c1是s[i]∈['1'，'9']，条件c2是s[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}