题解 | 数字字符转化为字母组合的种数

package main

import (
    "fmt"
)

func main() {
    var str string
    for {
        n, _ := fmt.Scan(&str)
        if n == 0 {
            break
        } else {
            fmt.Println(process(str, 0))
        }
    }
}
// func process(str string, i int) int {
// 	if i == len(str) {
// 		return 1
// 	}
// 	if i > len(str) {
// 		return 0
// 	}

// 	sum := 0
// 	if str[i] == '1' {
// 		sum += process(str, i+1) + process(str, i+2)
// 	} else if str[i] == '2' {
// 		sum = process(str, i+1) 
// 		if i+1 < len(str) && str[i+1] >= '0' && str[i+1] <= '6'{
// 			sum += process(str, i+2) 
// 		}
// 	} else if str[i] == '0' [
// 		sum = 0
// 	] else {
// 		sum = process(str, i+1)
// 	}
// 	return sum
// }
func process(str string, i int) int {
	// 先搞递归，再搞dp 
    // 对应初始化条件
  // i == len(str) ,  dp[i] = 1
  // i > len(str), dp[i] = 0
    dp := make([]int, len(str)+2)
    dp[len(str)] = 1
	// 从后往前，要求的答案为dp[0]
    for i:=len(str)-1; i>=0; i-- {
	    // 全部抄过来，process返回的就是dp[i+1], dp[i+2]对应的值
        if str[i] == '1' {
            dp[i] = dp[i+1] + dp[i+2]
        } else if str[i] == '2' {
            dp[i] = dp[i+1]
            if i+1 < len(str) && str[i+1] >= '0' && str[i+1] <= '6' {
                dp[i] += dp[i+2]
            } 
        } else if str[i] == '0' {
            dp[i] = 0
        } else {
            dp[i] = dp[i+1]
        }
        dp[i] = dp[i] % (1e9+7)
    }
    
    return dp[0]
}