Perfect Square Number | 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 279. Perfect squares

Given a positive integer n, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to n. You want to minimize the number of perfect squares that make up the sum.

Given an integer n, return the minimum number of perfect squares that sum to n.

A perfect square is an integer whose value equals the square of another integer; In other words, its value is equal to the product of an integer. For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.

Example 1:

Enter n = 12

Output: 3

12 = 4 + 4 + 4

Example 2:

Enter: n = 13

Output: 2

13 = 4 + 9

1 <= n <=
$10^4$

—

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

Reference code

The language version

func numSquares(n int) int {
    dp:=make([]int,n+1) // Default initialization values are 0
    for i:=1; i<=n; i++{ dp[i]=i// The worst case is +1 each time
    }
    for i:=2; i<=n; i++{for j:=0; j*j<=i; j++{ dp[i]=Min(dp[i],dp[i-j*j]+1)}}return dp[n]
}

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





Copy the code

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

Java version

    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // Default initialization values are 0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // The worst case is +1 each time
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // Dynamic transfer equation}}return dp[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.