This is the 24th 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


This is a simple question šŸ˜„šŸ˜„šŸ˜„ \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

Tip:

1 <= n <=
1 0 4 10^4

—

ā¤ ļø ā¤ ļø ā¤ ļø ā¤ ļø

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

The last step

If n is equal to 81, then the worst case you need is the sum of n times, which is the same thing as adding n ones

The best case is once, just one perfect square, which we can store in an array, for example d[5] = d[4] + 1

We define d[n] to be the minimum number of perfect squares that sum to n

By the question, x2 + y2 = nx y ^ ^ 2 + 2 = nx2 + y2 = n – > n – y2 > = 0 n – y ^ 2 > = 0 n – y2 > = 0

It is obvious that y starts at 1 until nāˆ’y2>=0n āˆ’y ^2 >=0n āˆ’y2>=0. In the example above, nāˆ’y2<0n āˆ’y ^2 <0n āˆ’y2<0 is the last step when y increases to the maximum value that satisfies the condition.

For example, d[5]=5āˆ’22d[5] = 5-2 ^2d[5]=5āˆ’22, y = 2, n =5 is the last step, and we only need to calculate the values of D [5] and d[4] + 1.

1.2. Dynamic programming component 2: Transfer equation

d[n] = min{d[n], d[n – y^2] + 1}

1.3. Dynamic programming component 3: initial conditions and boundary cases

Zero initializations.

1.4. Dynamic programming component 4: Order of calculation

Every n matches y. (y ranges from 1 to n – y^2)

Time complexity: square root of n * n

Space complexity: n, using a one-dimensional array dp.


Great! šŸ˜„ šŸ˜„ šŸ˜„ \ 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


N I C E Easy šŸ˜„šŸ˜„šŸ˜„ \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.