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

动态规划

• dp[i] ：前 i 个字符的子串，转化为字母组合的方案。
• dp[i] 的结果与前 i-1 个字符组成的子串相关。
  1. 如果第 i 个字符只能够单独转换为一个字母（比如说 str(i)='8'），则前 i 个子符转化为 字符的方案数 与 前 i-1 个字符的方案数相同。
  2. 如果第 i 个字符能够和第 i-1 个字符组合转换为一个字母，则第 i 个字符有两种转换为 字母 的可能：

     （1） 第 i 个字符单独转换为 字母（和第一种情况一样）
     （2） 结合第 i-1 个字符，组合转换为 字母，如果是这种情况，那么，需要找出第 i-1 个字符单独转换为 字母 的方案数。因此，这种情况下，方案数 与 第 i-1 个字符单独转换为字母的方案数相同。

递推式

// 第 i 个字符只能单独转换为一个 字母
// dp[i-1] ：第 i 个字符单独转换的方案数
dp[i]=dp[i-1];
// 第 i 个字符 可以和 第 i-1 个字符 共同转换为一个 字母
// dp[i-1] ：第 i 个字符单独转换的方案数
// dp[i-2] ：第 i 个字符，结合第 i-1 个字符组合转换为一个字母的方案数
dp[i]=dp[i-1]+dp[i-2];

题解

public class Main {
    private static String num;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        num = in.next();
        num = "0" + num;
        System.out.println(findLetter());
    }
    private static int findLetter() {
        int[] dp = new int[num.length() + 1];
        // 初始化 1：表示第 1 个字符只能有 1 种转换情况
        dp[0] = 1;
        for (int i = 1; i < num.length(); ++i) {
            // 判断第 i 个字符能够转换为 字母的情况
            // 0 不能转换
            // 1 第 i 个字符只能单独转换为一个字母
            // 2 第 i 个字符能够结合第 i-1 个字符转换为 一个字母
            int judge = judge(i);
            if (judge == 0) {
                return 0;
            }
            if (judge == 1) {
                // dudge=1
                dp[i] = dp[i - 1];
            } else {
                // judge=2
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
        }
        return dp[num.length() - 1];
    }
    // 判断第 i 个字符能够转换为 字母的情况
    private static int judge(int i) {
        int count = 0;
        if (num.charAt(i) >= '1' && num.charAt(i) <= '9') {
            // 能够单独转换
            count++;
        }
        if (num.charAt(i - 1) != '0') {
            int letter = Integer.valueOf(num.substring(i - 1, i + 1));
            if (letter >= 10 && letter <= 26) {
                // 能够结合第 i-1 个字符一起转换
                count++;
            }
        }
        return count;
    }
}

#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007;

int main(){
    string s;
    cin>>s;
    int l = s.length(), p=1;
    int cnt = (s[l-1]=='0'?0:1);
    for(int i=l-2;i>=0;i--){
        if(s[i]=='0'){
            p = cnt;
            cnt = 0;
        }else{
            int t = cnt;
            if((10*(s[i]-'0')+s[i+1]-'0')<=26)
                cnt = (cnt+p)%M;
            p = t;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int cur = s[s.size() - 1] == '0' ? 0 : 1;
	int next = 1, tmp = 0;
	for (int i = s.size() - 2; i >= 0; i--){
		if (s[i] == '0'){
			next = cur;
			cur = 0;
		}
		else{
			tmp = cur;
			if ((s[i] - '0') * 10 + s[i + 1] - '0' < 27)
				cur = (cur+next)%1000000007;
			next = tmp;
		}
	}
	cout<< cur%1000000007;
    return 0;
}

import java.util.*;

public class Main {
    public static int mod = (int)1e9 + 7;
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(dpComboNum(s));
    }
    /*
    public static long getComboNum (char[] arr, int index) {
        if (index == arr.length)
            return 1;
        if (arr[index] == '0')
            return 0;
        if (arr[index] == '1') {
            long res = getComboNum(arr, index+1) % mod;
            if (index + 1 < arr.length) {
                res += getComboNum(arr, index+2) % mod;
            }
            return res % mod;
        }
        if (arr[index] == '2') {
            long res = getComboNum(arr, index+1) % mod;
            if (index + 1 < arr.length && (arr[index+1] >= '0' && arr[index + 1] <= '6')) {
                res += getComboNum(arr, index+2) % mod;
            }
            return res % mod;
        }
        return getComboNum(arr, index+1) % mod;
    }*/
    public static int dpComboNum(String strs) {
        if (strs == null || strs.charAt(0) == '0' || strs.length() == 0)
            return 0;
        int n = strs.length();
        int[] dp = new int[n+1];
        dp[n] = 1;
        for (int i = n-1; i >= 0; i--) {
            dp[i] = dp[i+1];
            if (strs.charAt(i) == '0')
                dp[i] = 0;
            if (strs.charAt(i) == '1') {
                if (i + 1 < n) {
                    dp[i] = (dp[i] + dp[i+2]) % mod;
                }
            }
            if (strs.charAt(i) == '2') {
                if (i + 1 < n && (strs.charAt(i+1) >= '0' && strs.charAt(i+1) <= '6')) {
                    dp[i] = (dp[i] + dp[i+2]) % mod;
                }
            }
        }
        return dp[0];
    }
}

#include<iostream>
#include<cstring>
using namespace std;
const int mod = 1e9+7;
int proccess(string &s,int i) {
    if (i==s.size()) return 1;
    if (s[i] == '0') return 0;
    int res = proccess(s, i+1) % mod;
    if(i+1 < s.size()) {
        int num = (s[i]-'0')*10 + s[i+1]-'0';
        if(num>=0 && num <=26) res = (res + proccess(s,i+2) ) % mod;
    }
    return res;
}
int main() {
    string s;
    cin>>s;
    int n = s.size();
     
    
    if(s[0]==0) {
        puts("0");
        return 0;
    }
    int res = proccess(s,0);
    cout << res << endl;
    
    
    
}

#include<cstdio>
(802)#include<cstring>
const int mmax=100010;
char str[mmax];
int dp[mmax];
int main(){
    scanf("%s",str+1);
    dp[0]=1;
    if(str[1]!='0')
        dp[1]=1;
    //printf("%d",strlen(str+1));
    for(int i=2;i<=strlen(str+1);++i){
        if(str[i]!='0'){
           dp[i]=(dp[i]+dp[i-1])%1000000007;        
        }
        int sum=(str[i-1]-'0')*10+str[i]-'0';
        if(sum>=10&&sum<=26){
            dp[i]=(dp[i]+dp[i-2])%1000000007;
        }
        //printf("%d %d\n",i,dp[i]);
    }
    printf("%d",dp[strlen(str+1)]);
}