【编程题】将给定的数转换为字符串，原则如下：1对应 a，2对

public static int cal26(String num){
        int len = num.length();
        if (len==1){
            return 1;
        }else if (len==2) {
            if (Integer.parseInt(num)<=26){
                return 2;
            }else {
                return 1;
            }
        }else{
           return cal26(num.substring(1,len))+
                   ((cal26(num.substring(0,2)))-1)*cal26(num.substring(2,len));
        }
    }

类似排列组合中的插空法.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
    string str = "121212";
    int n = str.size();
    vector<int>f(n + 1);
    f[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (str[i] == '0') {
            f[i] = 0;
        }
        else {
            f[i] = f[i + 1];
            if (i < n - 1) {
                int num = (str[i] - '0') * 10 + str[i + 1] - '0';
                if (num <= 26) {
                    f[i] += f[i + 2];
                }
            }
        }
    }
    cout << f[0] << endl;
}

public int method(int num) {
        String s = String.valueOf(num);
        char[] chars = s.toCharArray();
        int[] dp = new int[chars.length+1];
        dp[0] = 1;
        dp[1] = chars[0]-'0'==0?0:1;
        for (int i = 2; i < chars.length+1; i++) {
            //当前位的值如果是0，有没有这位没有区别，dp[i]的值等于dp[i-1]
            int one = chars[i-1]-'0';
            if (one != 0){
                dp[i] += dp[i-1];
            }
            //如果前一位的值是0，就没有必要考虑这两位放在一起了
            //如果前一位不是0，那么这两位就肯定是10以上
            if (chars[i-2]-'0' == 0){
                continue;
            }
            //如果这两位小于等于26，就可拆可合，上上位的值再加上
            int two = (chars[i-2]-'0')*10+(chars[i-1]-'0');
            if (two <= 26){
                dp[i] += dp[i-2];
            }
        }
        return dp[chars.length];
    }

int maxTrans(string s)
{
	vector<int> dp(s.size() + 1);
	dp[s.size()] = 1;
	dp[s.size() - 1] = (s[s.size() - 1] == '0' ? 0 : 1);
	for (int i = s.size() - 2; i >= 0; --i)
	{
		if (s[i] == '0')
			dp[i] = 0;
		else
			dp[i] = dp[i + 1] + ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26 ? dp[i + 2] : 0);
	}
	return dp[0];
}

先设一个一维数组res[]，res[i]代表以i结束时有多少中组合，那么i+1位置上的组合数就是：
（1） 当i位置上的数字小于等于2且i+1位置上的数小于等于6时（也即时i与i+1组成的数小于26，
     也即是他们一起可以表示一个字母）此时res[i+1] = res[i] + res[i-1]；注意判断i-1下标
     是否越界；
（2）否则res[i+1] = res[i];
举例：输入为 123456789，那么res数组为 1,2,3，3,3,3,3,3,3。 
public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  char[] cs = br.readLine().trim().toCharArray();   int len = cs.length;  int[] res = new int[len];    res[0] = 1;  for (int i = 1; i < len; i++) {  if (cs[i - 1] - '0' <= 2 && cs[i] - '0' <= 6) {  if (i - 2 >= 0)
                res[i] = res[i - 1] + res[i - 2];  else    res[i] = res[i - 1] + 1;    } else    res[i] = res[i - 1];    }
    System.out.println(res[len - 1]); }