文章目录

• 题目描述
• 思路及解答

题目描述

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:

输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路及解答

/*
思路：
https://blog.csdn.net/u012156116/article/details/79763005
1.利用动态规划解答，相当于上楼梯的变形
2.首先，如果第一位上是0，那么无法转码，返回0；
3.其次，每次转码，都可以看看第i位跟第i-1位的数字是否小于等于26，如果符合的话，我们在i-2位上解码；如果第i位不等于0的话，说明我们相当于在第i-1位上解码。如果两个都符合，相当于：dp[i] = dp[i-1] + dp[i-2];
*/
import java.util.Scanner;

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String str=input.next();
        String[] strs=str.split("");
        int len=strs.length;
        int[] dp=new int[len+1];
        dp[0]=1;
        dp[1]=1;
        for (int i = 2; i < len+1; i++) {    
            if(strs[i-1].equals("0")){
                dp[i]=dp[i-2];
            }
            int tmp=Integer.parseInt(strs[i-2]+strs[i-1]);
            if(tmp>26){
                dp[i]=dp[i-1];
            }else{
                dp[i]=dp[i-1]+dp[i-2];
            }
        }
        input.close();
        System.out.println(dp[len]);
    }
}