解码方法

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        System.out.println(numDecodings(s));
    }

    public static int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            //如果该位不为'0'，说明该位单独成字母合法
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            //如果后两位能组成"1x"（x为任意数字）或者"2x"（x小于7），说明最后两位组成字母合法
            if ((s.charAt(i - 2) == '1') || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

"""
递归求解解码种数
满足条件10--26时 decoder(s[:]) = decoder(s[1:]) + decoder(s[2:])
否则 decoder(s[:]) = decoder(s[1:])
"""
import sys


def decoder(s):
    if not s:
        return 1
    ret = decoder(s[1:])
    if len(s) >= 2:
        if ord(s[0]) == ord('1') or (ord(s[0]) == ord('2') and ord('0') <= ord(s[1]) <= ord('6')):
            ret += decoder(s[2:])
    return ret


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    s = input().strip()
    ans = decoder(s)
    print(ans)

	

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]){
    string str;
    cin >> str;
    int f0 = 1, f1 = 1, f;
    for(int idx = 1; idx < str.length(); idx++){
        int code = (str[idx-1]-'0')*10+(str[idx]-'0');
        f = 0;
        if(code >= 1 && code <= 26) f += f0;
        if(str[idx] != '0') f += f1;
        
        f0 = f1;
        f1 = f;
        if(f1 == 0) break;
    }
    cout << f1 << endl;
    return 0;
}

n = input()
count = [0 for i in range(len(n))]
if  n=="0":
    print(0)
else:
    if n[0]=="0":
        count[0]=0
    else:
        count[0]=1
    if n[1]!="0":
        t1=1
    else:
        t1=0
    if n[0]=="1" or (n[0]=="2" and int(n[1])<=6):
        t2=1
    else:
        t2=0
    count[1]=t1+t2
    for i in range(2,len(n)):
        if n[i]!="0":
            count[i]+=count[i-1]
        if int(n[i-1:i+1])>=10 and int(n[i-1:i+1])<=26:
            count[i] +=count[i-2]
    print(count[len(n)-1])

解析:依然是将对应位置的结果存入数组中，记录状态。在每一个阶段时，考虑当前字符串是否可独立（是否为0），是否可与前一个字符串相结合这两种情况，如果可独立，这是的第i阶段的方法总数就加上前一阶段的方法总数，如果可合并就加上前两个阶段的方法总数，每一个阶段的初始化为零。

直接dp

1. import java.util.Scanner;
2. import static java.lang.System.in;
3. public class Main {
4.     public static void main(String[] args) {
5.         Scanner sc = new Scanner(in);
6.         String n = sc.nextLine();
7.         System.out.println(dpProcess(n.toCharArray()));
8.     }
9.     public static int dpProcess(char[] str) {
10.         int len = str.length;
11.         int[] dp = new int[len + 1];
12.         dp[len] = 1;
13.         dp[len - 1] = 1;
14.         for (int i = len - 2; i >= 0; i--) {
15.             if (str[i] == '1' || (str[i] == '2' && str[i + 1] <= '6')) {
16.                 dp[i] = dp[i + 1] + dp[i + 2];
17.             }
18.             else{
19.                 dp[i] = dp[i + 1];
20.             }
21.         }
22.         return dp[0];
23.     }
24. }

#include <bits/stdc++.h>
using namespace std;

int cnt = 0, l;

void F(string s){
    int m = s.length();
    if(s=="" || m==0){
        cnt++;
        return ;
    }
    if(m>=2 && (s[0]=='1' || (s[0]=='2' && s[1]<='6'))){
        F(s.substr(2));
        F(s.substr(1));
    }else
        F(s.substr(1));    
}

int main(){
    string s;
    while(cin>>s){
        l = s.length();
        F(s);
        cout<<cnt<<endl;
    }
    return 0;
}

暴力递归

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        System.out.println(dfs(str, 0));
    }
    
    private static int dfs(char[] str, int depth) {
        if(depth >= str.length){
            // 字符串末尾匹配完了，增加一种翻译方案
            return 1;
        }else{
            if(str[depth] == '0'){
                // 本层单独面对一个0，之前的翻译有误，这个0应该与前一个字符结合
                return 0;
            }
            // 本层字符单独成为一种翻译
            int ways = dfs(str, depth + 1);
            if(str[depth] == '1' && depth < str.length - 1){
                // str[depth]与str[depth + 1]翻译成j~s
                ways += dfs(str, depth + 2);
            }else if(str[depth] == '2' && depth < str.length - 1 && (str[depth + 1] >= '0' && str[depth + 1] <= '6')){
                // str[depth]与str[depth + 1]翻译成t~z
                ways += dfs(str, depth + 2);
            }
            return ways;
        }
    }
}

使用 dp，每个数字单独看待或者作为个位看待。

例如：12

1. 这个 1 没什么说的：只能作为一个单独的数字看待。

2. 这个 2 可分两种情况：

   1. 单独作为数字 2 。
   2. 作为数字 12 的个位数字。

最后：因为 0 比较特殊（不能作为单独的数字存在），需要注意一下。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for(int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            dp[i + 1] = ch != '0' ? dp[i] : 0;
            if(i > 0 && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && ch <= '6'))) {
                dp[i + 1] += dp[i - 1];
            }
        }
        System.out.println(dp[s.length()]);
    }
}

package main

import (
    "fmt"
)


func main(){
    str := ""
    fmt.Scan(&str)
    n := len(str)

    dp := make([]int, n+2)
    dp[0] = 1
    dp[1] = 2

    for i := 2 ; i < n ; i++ {

        if str[i-1] <= '2' && str[i] <= '6' {
            dp[i] = dp[i-2] + dp[i-1]
        }else{
            dp[i] = dp[i-1]
        }
    }
    fmt.Println(dp[n-1])
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(DecodeCount(s));
    }
    public static int DecodeCount(String strs){
        int[] s = new int[strs.length()];
        for(int i = 0; i < strs.length(); i++){
            char c = strs.charAt(i);
            s[i] = c - '0';
        }
        int[] dp = new int[strs.length()];
        if(s[0] == 0)   return 0;
        dp[0] = 1;
        if (s[0] * 10 + s[1] <= 26 && s[0] * 10 + s[1] > 0){
            dp[1] = s[1] == 0 ? 1 : 2;
        }else{
            if(s[1] == 0)   return  0;
            dp[1] = 1;
        }
        for(int i = 2; i < s.length; i++){
            if(s[i - 1] * 10 + s[i] <= 26 && s[i - 1] * 10 + s[i] > 0){
                dp[i] = s[i] == 0 ? dp[i - 2] : dp[i - 2] + dp[i - 1];
            }else{
                if(s[i] == 0)   return 0;
                dp[i] = dp[i - 1];
            }
        }
        return dp[strs.length() - 1];
    }
}

//对于12122 可以组成四个两位数，则dp[4]=dp[4-4]*(2^4-2^3)
//对于121 可以组成两个两位数 dp[2]=dp[2-2]*(2^2-2^1);
//对于12  可以组成一个两位数 dp[1]=dp[1-1]*2;
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
int main()
{
    string s;
    while (cin >> s)
    {
        vector<int> dp(s.size() + 1, 0);
        if (s.size() == 0) { cout << 0 << endl; break; }
        if (s.size() == 1) { cout << 1 << endl; break; }
        if (s.size() == 2) {
            int temp = s[0] - '0';
            temp = temp * 10 + s[1] - '0';
            if (temp <= 26 && temp >= 11)
                cout << 2 << endl;
            else cout << 1 << endl;
            break;
        }
        dp[0] = 1; int flag = 0;
        for (int i = 1; i <= s.size(); i++)
        {
            int temp = s[i - 1] - '0';
            temp = temp * 10 + s[i] - '0';
            if (temp <= 26 && temp >= 11)
            {
                if (flag)
                    if (flag >= 2)
                        dp[i] = dp[i - flag] * (pow(2, flag) - pow(2, flag - 1));
                    else
                        dp[i] = dp[i - 1] + 1;
                else
                    dp[i] = dp[i - 1] * 2;
                flag ++;
            }
            else {
                dp[i] = dp[i - 1]; flag = 0;
            }
        }
        cout << dp[s.size() - 1] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int df1(int y);
int df2(int y);

int main(){
    int n;
    cin>>n;
    int ans;
    ans = df1(n)+ df2(n);
    cout<<ans<<endl;
    return 0;
}
int df1(int y){
    int x = y % 10;
    int z = y / 10;
    if( x == 0) return 0;
    if( y <= 9) return 1;
    return df1(z)+df2(z);
}
int df2(int y){
    int x = y % 100;
    int z = y / 100;
    if(x <= 9 || x > 26)
        return 0;
    if(x <= 26 && z == 0)
        return 1;
    return df1(z) + df2(z);
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String num=in.next();
        System.out.println(deCode(num));
    }
    public static int deCode(String num){
        int len=num.length();
        int[] dp=new int[len];
        dp[0]=1;
        String str=num.substring(0,2);
        int strnum=Integer.parseInt(str);
        if(strnum>=1&&strnum<=26){
            dp[1]=2;
        }else{
            dp[1]=1;
        }
        for(int i=2;i<len;i++){
            String tmp=num.substring(i-1,i+1);
            int tmpnum=Integer.parseInt(tmp);
            if(tmpnum>=1&&tmpnum<=26){
                dp[i]=dp[i-2]+dp[i-1];
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[len-1];
    }
}

S = input()
out = [0]
for i in range(len(S)):
    if int(S[i])>2:
        out.append(i+1)
    if int(S[i])==2:
        if i<len(S)-1:
            if int(S[i+1])>6:
                out.append(i+1)
out.append(len(S))
temp = [1,1,2]
n = 3
num = 1
for i in range(len(out)-1):
    k = out[i+1]-out[i]
    while k>=n:
        temp.append(temp[n-1]+temp[n-2])
        n += 1
    num *= temp[k]
print(num)

s = input()

dp = [0] * len(s)
dp[0] = 1 if s[0] != '0' else 0
dp[1] = dp[0] + (1 if int(s[:2]) <= 26 and s[:2] != '00' else 0)

for i in range(2, len(s)):
    if s[i] != '0':
        dp[i] += dp[i-1]
    if s[i-1:i+1] != '00' and int(s[i-1:i+1]) <= 26:
        dp[i] += dp[i-2]
print(dp[-1])

python 动态规划

import sys
s=sys.stdin.readline().strip()
n=len(s)
dp=[1]*n
if int(s[0]+s[1])<=26:
    dp[1]=2
for i in range(2,n):
    if int(s[i-1]+s[i])<=26:
        dp[i]=dp[i-1]+dp[i-2]
    else:
        dp[i]=dp[i-1]
print(dp[-1])