Dynamic programming ing- Ugly number II | Go Theme month

[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.

$\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

$\color{green}{😄 😄 😄 ~}$

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

4. Comprehensive application

• Dynamic planning + hash
• Dynamic programming + recursion
• .

Leecode 264. Ugly numbers II

Given an integer n, please find and return the NTH ugly number.

Ugly numbers are positive integers that contain only prime factors 2, 3, and/or 5.

Example 1:

Enter n = 10

Output: 12

Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is a sequence of the first 10 ugly numbers.

Example 2:

Enter n = 1

Output: 1.

Explanation: 1 is usually considered an ugly number.

Tip:

1 <= n <= 1690

—

$\ color {green} {! 😄 😄 😄 ~}$

Reference code

The language version

func nthUglyNumber(n int) int {
    dp := make([]int, n+1)
    dp[1] = 1
    p2, p3, p5 := 1.1.1
    for i := 2; i <= n; i++ {
        x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
        dp[i] = min(min(x2, x3), x5)
        if dp[i] == x2 { 
            p2++   // The number of occurrences
        }
        if dp[i] == x3 {
            p3++
        }
        if dp[i] == x5 {
            p5++
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}






Copy the code

$\color{red}{NICE too simple 😄 😄 😄 ~}$

Java version

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if(dp[i] == num5) { p5++; }}returndp[n]; }}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.