目录

题目

输入描述:

输出描述:

示例1

输入

输出

说明

算法模型：

从i到n，i∈（0，n）：

模型特点：

用这个模型的题目有：

递归转动态规划：

思路分析：

暴力递归：

动态规划:

样例推导：

暴力递归：

动态规划：

代码展示:

暴力递归：

动态规划：

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1 

'B' -> 2 

... 

'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

输入描述:

12可以解码成“AB”，“L”这两种

输出描述:

解码方法的总数

示例1

输入

12

输出

2

说明

12可以解码成“AB”，“A，B"这两种

算法模型：

从i到n，i∈（0，n）：

模型特点：

定义函数info(i) 为从i到n的最优解，且info（i）会依赖于info(i+1) 或info(i+2) 或info(i+3)。具体依赖于哪个info，取决于当前的i，i+1,i+2。

用这个模型的题目有：

数字转换字符串安置路灯

递归转动态规划：

每次递归都依赖后几个info。所以每一个info都会计算许多次用动态规划，自底向上，先求出info(n)的值，在求出info(n-1).....依次往前求

思路分析：

暴力递归：

定义一个info函数，用来递归
info(i)表示，从i到n-1的解，即从i到n-1一共有多少种可能
从i=0开始，分情况讨论
如果调用函数时i>=n.
info(i)返回唯一的一种可能
如果当前字符atChar(i)==0，说明当前字符不能作为数字开头
info(i)返回0
如果当前字符atChar(i)与下一个字符atChar(i+1)组成的数字小于27，说明可以为一位数组成字母，或者两位数组成字母
info(i)返回info(i+1)+info(i+2)
如果当前字符atChar(i)与下一个字符atChar(i+1)组成的数字大于27，说明只能是一个数字构成字母
info(i)返回info(i+1)

动态规划:

定义一个dp数组，用来存储动态规划的结果
dp[i]表示，从i到n-1的解，即从i到n-1一共有多少种可能
从n-1开始，直接给出dp[n-1],dp[n-2],从后向前遍历字符串
如果当前字符atChar(i)==0，说明当前字符不能作为数字开头
dp[i]=0
如果当前字符atChar(i)与下一个字符atChar(i+1)组成的数字小于27，说明可以为一位数组成字母，或者两位数组成字母
dp[i] = dp[i+1] + dp[i+2]
如果当前字符atChar(i)与下一个字符atChar(i+1)组成的数字大于27，说明只能是一个数字构成字母
dp[i] = dp[i+1]

样例推导： 暴力递归：

动态规划：

代码展示: 暴力递归：

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

public class Main{
    private static String str;
    static int info(int i){
        if(i >= str.length()){
            return 1;
        }
        if(str.charAt(i) == '0'){
            return 0;
        }
        if(i == str.length()-1){
            return 1;
        }
        if(((str.charAt(i)-'0')*10+(str.charAt(i+1)-'0')) <27){
            return info(i+1)+info(i+2);
        }else{
            return info(i+1);
        }
    }
    
    public static void main(String[] args)throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        str = reader.readLine();
        System.out.println(info(0));
    }
}

动态规划：

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

public class Main{
    private static String str;
    private static int dp[];
    private static int n;
    static int StringCharAtToInt(int i){
        return str.charAt(i)-'0';
    }
    private static void info(){
        dp[n-1] = 1;//初始化dp后两位
        if((StringCharAtToInt(n-2)*10+StringCharAtToInt(n-1)) < 27){
            dp[n-2] = 2;
        }else{
            dp[n-2] = 1;
        }
        
         
        for(int i=str.length()-3;i>=0;i--){//根据后面的dp求前面的dp
            if(StringCharAtToInt(i) == 0){
                dp[i] = 0;
            }
            else if(StringCharAtToInt(i)*10+StringCharAtToInt(i+1) < 27){
                dp[i] = dp[i+1] +dp[i+2];
            }else{
                dp[i] = dp[i+1];
            }
        }
    }
    
    public static void main(String[] args)throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        str = reader.readLine();
        n = str.length();
        dp = new int[n];
        info();
        System.out.print(dp[0]);
    }
}