LeetCode_ Dynamic programming_ Medium_ 91. decoding method

1. subject

One contains letters A-Z The message is mapped as follows code ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message , All numbers must be based on the above mapping method , Back to letters （ There may be several ways ）. for example ,“11106” It can be mapped to ：
① “AAJF” , Group messages into (1 1 10 6)
② “KJF” , Group messages into (11 10 6)
Be careful , Messages cannot be grouped into (1 11 06) , because “06” Cannot map to “F” , This is because “6” and “06” It's not equivalent in mapping .

Give you a non empty string containing only numbers s , Please calculate and return the total number of decoding methods .

The question data guarantee that the answer is definitely one 32 An integer .

Example 1：
Input ：s = “12”
Output ：2
explain ： It can be decoded as “AB”（1 2） perhaps “L”（12）.

Example 2：
Input ：s = “226”
Output ：3
explain ： It can be decoded as “BZ” (2 26), “VF” (22 6), perhaps “BBF” (2 2 6) .

Example 3：
Input ：s = “0”
Output ：0
explain ： No characters are mapped to 0 Number at the beginning .
contain 0 The effective mapping of is ‘J’ -> “10” and ‘T’-> “20” .
Because there are no characters , So there is no effective way to decode this , Because all numbers need to be mapped .

Tips ：
1 <= s.length <= 100
s Numbers only , And may contain leading zeros .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/decode-ways

2. Ideas

（1） Dynamic programming
hypothesis dp[i] Express s[0…i - 1] Number of decoding methods , And set dp[0] = 1. We can know from the analysis that State transition relationship as follows ：
① If s[i] Itself can represent a letter , At this time, the number of decoding methods dp[i] = dp[i - 1];
② If s[i] and s[i - 1] Stitching together can represent a letter , At this time, the number of decoding methods dp[i] = dp[i - 2];

If ① ② At the same time satisfy , be dp[i] = dp[i - 1] + dp[i] = dp[i - 2]; If they are not satisfied , be dp[i] = 0（ Default value ）.

3. Code implementation （Java）

// Ideas 1———— Dynamic programming 
class Solution {
    
    public int numDecodings(String s) {
    
        int length = s.length();
        if (length < 1) {
    
            return 0;
        }
        //dp[i] Express s[0...i - 1] Number of decoding methods 
        int[] dp = new int[length + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= length; i++) {
    
            char c1 = s.charAt(i - 1);
            char c2 = s.charAt(i - 2);
            if (c1 >= '1' && c1 <= '9') {
    
                // s[i]  Itself can represent a letter 
                dp[i] += dp[i - 1];
            }
            if (c2 == '1' || c2 == '2' && c1 <= '6') {
    
                // s[i]  and  s[i - 1]  Stitching together can represent a letter 
                dp[i] += dp[i - 2];
            }
        }
        return dp[length];
    }
}