leetcode91

解码方法：https://leetcode.cn/problems/decode-ways/submissions/

思路：题目中要求求出数字到字母的映射，需要注意前导零的处理，像这种全局最优依赖于局部最优的问题就需要使用动态规划来求解了。

首先对字符串进行遍历，每次都需要考虑前一位的数字，用a代表当前位置的数字，用b代表前一位与当前位置组成的数字，如果b能组成满足题目的数字的话(也就是b>=10&&b<=26)，那么就代表有更多的映射方法，也就是当前位置就可以由 第i-1位数字和第i-2位数字共同组成。否则当前位置的方法数和前一位的方法数一样。

根据题目的意思可以列出以下的公式：

F[i] = F[i-1] ,  a>=1&& a <=9 

F[i] += F[i-2], b>=10&& b<=26

func numDecodings(s string) int {
    n:= len(s)
    if s[0] == '0'{
        return 0
    }
   
    dp := make([]int,n+1)
    dp[0] = 1
    for i:= 1; i< n; i++ {
        num1 := (s[i-1] - '0') * 10 + s[i] -'0'
        num2 := s[i] - '0'
        if num2 >=1 && num2 <=9 {
            dp[i] = dp[i-1]
        }
        if num1 <=26 && num1 >=10 && i >=2{
            dp[i] += dp[i-2]
        } else if num1 <=26 && num1 >=10 && i ==1{
            dp[i]+=1
        }
        
    
    }
    return dp[n-1]
}

放张图激励下自己：