This is the 22nd day of my participation in Gwen Challenge


If you are not familiar with dynamic programming, please refer to this chapter \color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 91. Decoding method

A message containing the letters A-Z is encoded by the following mapping:

‘A’ -> 1

‘B’ -> 2

.

‘Z’ -> 26

To decode the encoded message, all numbers must be mapped back to letters, based on the above method of mapping (there may be several methods).

For example, “111” could map each “1” in “1” to “A” to get “AAA”, or it could map “11” and “1” (“K” and “A” respectively) to “KA”. Note that “06” cannot be mapped to “F” because “6” is different from “06”.

Given a non-empty num string containing only numbers, count and return the total number of decoding methods.

The data guarantees that the answer is a 32 – digit integer.

Example 1:

Input: s = “12” Output: 2 Explanation: It can be decoded as either “AB” (1, 2) or “L” (12).

Example 2:

Input: s = “226” Output: 3 Explanation: It can be decoded to “BZ” (2 26), “VF” (22 6), or “BBF” (2 26).

Example 3:

Input: s = “0” Output: 0 Description: No character maps to a number starting with 0. Valid mappings with 0 are ‘J’ -> “10” and ‘T’-> “20”. Since there are no characters, there is no efficient way to decode this because all numbers need to be mapped.

Example 4:

Input: s = “06” Output: 0 Explanation: “06” cannot be mapped to “F” because a 0 at the beginning of a string cannot point to a valid character.

Tip:

1 <= S. length <= 100 s contains only numbers and may contain leading zeros.

—

In fact, this problem mainly consider the boundary >6 numbers = 0 numbers can pass. ❤ ️ ❤ ️ ❤ ️ ❤ ️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

2.2. Dynamic programming component 3: Initial conditions and boundary cases

Initial conditions:

Numbers starting with or ending with 0 are not acceptable except 10 or 20.

See code ~~ for details

2.3. Dynamic programming component 4: Calculation sequence

In turn,

Reference code

The language version

 func numDecodings(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    dp := make([]int, n+1)
    dp[0] = 1
    if s[0] = ='0' {
        dp[1] = 0
    } else {
        dp[1] = 1
    }
    for i := 1; i < n; i++ {
        if s[i- 1] = ='1' || (s[i- 1] = ='2' && s[i] < '7') {
            // If it is 20, 10
            if(s[i] == '0') {
                dp[i + 1] = dp[i - 1]}else { // // If it is 11-19, 21-26
                dp[i + 1] = dp[i] + dp[i - 1]}}else if(s[i] == '0') {// if 0, 30, 40, 50
            return 0
        } else {
             // I -1 and I do not form the same letter
             dp[i + 1] = dp[i]
        }
    
    }
     return dp[n]
}

Copy the code

JAVA version

  public int numDecodings(String s) {
        int n = s.length();
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) = ='0' ? 0 : 1;
        for(int i = 1; i < n; i++){

            if(s.charAt(i-1) = ='1' || s.charAt(i-1) = ='2' && s.charAt(i) <'7') {// If it is 20, 10
                if(s.charAt(i) == '0') dp[i + 1] = dp[i - 1];
                    // If it is 11-19, 21-26
                else dp[i + 1] = dp[i] + dp[i - 1];
            }else if(s.charAt(i) == '0') {// if 0, 30, 40, 50
                return 0;
            }else{
                // I -1 and I do not form the same letter
                dp[i + 1] = dp[i]; }}return dp[n];

    }
    @Test
    public void isnumDecodings(a) {
        int i = numDecodings("100");
        Assert.assertNotNull(i);
    }
    

Copy the code

❤ ️ ❤ ️ ❤ ️ ❤ ️

Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much!

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.