数字字符转换为字母组合的种数

要求多少种不同的转换结果
每个位置我们都应该去两种选择

1. 当前位
2. 当前位和下一位

但是要求 O（n） 和 O（1）
就绝不可能是动态规划了
我们可先不考虑空间复杂度
分解一下问题
假设 dp[i] 标示前i个子串转化为字母组合的方案
则

1. 如果第i个字母可以单独转换，则 dp[i] = dp[i]-1
2. 如果第i个字母与i-1 可以组合成一个字母则可以表述为
   2.1 第i个字母组合数= 前一个字符的组合数（单个转换）+ 前两个字符的组合数（组合转换） dp[i] = dp[i-1]+dp[i-2]

为了方便处理我们定义 dp 数组范围 从 0 - n+1 如 ：dp[0~n+1]
dp[0] = 1 //因为只有 dp[i-2] 会用到，默认取1，用那个与 i< 2 的时候作为累加值计算
dp[1] = str[i] != 0 ? 1 : 0

package main
import (
    "fmt"
    "strconv"
)
func main(){
    var str1 string
    fmt.Scanf("%s",&str1)
    helper(str1,len(str1))
    return 
}
//获取当前i位置 可以转换的类型，0 标示不能转换 1标示只能单独 2标示可以组合
func getType(str string ,i,n int) int {
    if i>=n || i==0{
        return 0
    }
    count := 0
    if str[i] <= '9' && str[i] >='1'{
        count++
    }
    if str[i-1] != '0' {
        num ,_ := strconv.Atoi(string(str[i-1:i+1]))
        if num >=10 && num <27{
            count++
        }
    }
    return count
}
//基于此，用 变量替换 dp[i-1] ,dp[i-2] 即可
func helper(str string,n int){
    if n == 0 {
        return 
    }
    //res := 0
    dp := make([]int,n+1)
    dp[0] = 1
    if str[0] != '0'{
        dp[1] = 1
    }

    for i:=2;i<=n;i++{
        tp := getType(str,i-1,n)
        //因为当前 为 0 标示没有可能了，无法向后走了
        if tp == 0 {
            break
        }
        if tp == 1{  //标示尽可以转换为一种
            dp[i] = dp[i-1]
        }else if tp == 2{//标示可以转换成两种
            //dp[i-1] 标示第i 个字符串单独的方案数
            //dp[i-2] 标示第 i 个字符串组合的方案数
            dp[i] = dp[i-1] + dp[i-2] 
        }
        dp[i]%=1000000007
    }
    fmt.Println(dp[n])
    return 

}