This is the 11th day of my participation in Gwen Challenge

Topic describes

This is LeetCode 279. Perfect squares, medium difficulty.

Tag: “Full knapsack”, “dynamic programming”, “Knapsack problem”

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:

Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4Copy the code

Example 2:

Input: n = 13 Output: 2 Description: 13 = 4 + 9Copy the code

Tip:

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

Complete knapsack (Simple solution)

First of all, there are an infinite number of perfect squares, but the number to make up is given.

Therefore, in the first step, “perfect squares” within the range of [1,n][1, n] can be preprocessed.

This step is to pre-process all possible “items”.

Thus, the problem is transformed into: given a number of numbers, each number can be used an infinite number of times, what is the minimum number of numbers needed to figure out the target value NNN.

Since the title does not limit us to use the same “perfect square number” only once, it belongs to the “perfect backpack” model.

The original state definition of the two types of knapsack problems we have studied so far (01 knapsack & full knapsack) is two dimensions:

  • The first dimension iii represents the item number

  • The second dimension, JJJ, represents the capacity

The second two-dimensional JJJ has two definitions: “no more than capacity JJJ” and “capacity is just JJJ”. In this case, we need to find the minimum number of NNN required by “just”.

So we can adjust our “state definition” :


f [ i ] [ j ] f[i][j] To consider before
i i Two numbers, sum them up
j j The minimum number of numbers required.

Without loss of generality, f[I][j]f[I][j]f[I][j]f[I][j]f[I][j] for the third number (assuming TTT), we have the following choices:

  • Selected 000 digital iii, there are f [I] [j] = f [I – 1) [j] [I] [j] f = f [I – 1) [j] [I] [j] f = f [I – 1) [j].
  • Selected 111 digital iii, there are f [I] [j] = f [I – 1) [j] – t + 1 f [I] [j] = f [I – 1) [j] – t + 1 f [I] [j] = f [I – 1) [j] – t + 1
  • Selected 222 digital iii, there are f [I] [j] = f [I – 1) [j] – 2 ∗ t + 2 f [I] [j] = f [I – 1) [j] – 2 * t + 2 f [I] [j] = f [I – 1) [j] – 2 ∗ t + 2…
  • Choose KKK digital iii, there are f [I] [j] = f [I – 1) [j] – k ∗ t + kf [I] [j] = f [I – 1] [j] – k * t + kf [I] [j] = f [I – 1) [j] – k ∗ t + k

Therefore, our state transition equation is:


f [ i ] [ j ] = m i n ( f [ i – 1 ] [ j – k ∗ t ] + k ) . 0 ⩽ k ∗ t ⩽ j f[i][j] = min(f[i-1][j-k*t]+k),0 \leqslant k * t \leqslant j

Of course, KKK numbers III can be selected only if the remaining j− K ∗ tj-K * Tj − K ∗t can also be rounded out by other “perfect squares”, The f [I – 1) [j] – k ∗ t f [I – 1] [j] – k * t f [I – 1) [j] – k ∗ t for meaningful value.

Code (for the naive complete knapsack problem, O(n2∗n)O(n^2 * \ SQRT {n})O(n2∗n), runs the risk of timeout, starting the subscript with 000, and the P2P2P2 code that handles the first item alone will just pass) :

class Solution {
    int INF = 0x3f3f3f3f;
    public int numSquares(int n) {
        // Preprocess all possible "perfect squares"
        List<Integer> list = new ArrayList<>();
        int t = 1;
        while (t * t <= n) {
            list.add(t * t);
            t++;
        }

        // f[I][j] represents the minimum number of elements used by j by considering the first I items
        int m = list.size();
        int[][] f = new int[m + 1][n + 1]; 
        
        // if f[0][0] is 0, all values are invalid
        Arrays.fill(f[0], INF);
        f[0] [0] = 0; 

        // Handle the rest of the case
        for (int i = 1; i <= m ; i++) {
            int x = list.get(i - 1);
            for (int j = 0; j <= n; j++) {
                // For the case where the ith number is not chosen
                f[i][j] = f[i - 1][j];
                // For k th th
                for (int k = 1; k * x <= j; k++) {
                    // We can select k x only if the rest of the numbers j - k * x can also be scraped out
                    if (f[i - 1][j - k * x] ! = INF) { f[i][j] = Math.min(f[i][j], f[i -1][j - k * x] + k); }}}}returnf[m][n]; }}Copy the code
class Solution {
    int INF = -1;
    public int numSquares(int n) {
        // Preprocess all possible "perfect squares"
        List<Integer> list = new ArrayList<>();
        int idx = 1;
        while (idx * idx <= n) {
            list.add(idx * idx);
            idx++;
        }

        // f[I][j] represents the minimum number of elements used by j by considering the first I items
        int len = list.size();
        int[][] f = new int[len][n + 1]; 
        
        // handle the first case
        for (int j = 0; j <= n; j++) {
            int t = list.get(0);
            int k = j / t;
            if (k * t == j) { // If the capacity is an integer multiple of the first number, it can be collected
                f[0][j] = k; 
            } else { // The rest are invalid values
                f[0][j] = INF; }}// Handle the rest of the case
        for (int i = 1; i < len; i++) {
            int t = list.get(i);
            for (int j = 0; j <= n; j++) {
                // For the case where the ith number is not chosen
                f[i][j] = f[i - 1][j];
                // For k th th
                for (int k = 1; k * t <= j; k++) {
                    // Can select k t if the rest of the numbers j - k * t can also be rounded
                    // Use 0x3f3f3f3f as the maximum value (reserved accumulative space) to omit this judgment
                    if (f[i - 1][j - k * t] ! = INF) { f[i][j] = Math.min(f[i][j], f[i -1][j - k * t] + k); }}}}return f[len - 1][n]; }}Copy the code
  • Time complexity: Preprocessing all possible digital complexity is O(n)O(\ SQRT {n})O(n), a total of N ∗nn * \ SQRT {n}n∗ N states need to be transferred, and each state transfer is traversed NNN times at most. Therefore, after all states are transferred, the complexity is O(n2∗n)O(n^2 * \ SQRT {n})O(n2∗n). The overall complexity is O(n2∗n)O(n^2 * \ SQRT {n})O(n2∗n).
  • Space complexity: O(n∗n)O(n * \ SQRT {n})O(n∗n).

Full backpack (Advanced)

Obviously the naive version of the full knapsack is a little bit more complicated.

This time we will do the derivation again in accordance with the same idea to strengthen the understanding of this “one-dimensional space optimization” method.

Start with the two-dimensional state transition equation for analysis (assuming TTT as the third number) :

So far, we have obtained the final state transition equation:


f [ j ] = m i n ( f [ j ] . f [ j – t ] + 1 ) f[j] = min(f[j], f[j – t] + 1)

Meanwhile, the logic of pre-processing “items” can be directly transferred to the transfer process.

Code:

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int t = 1; t * t <= n; t++) {
            int x = t * t;
            for (int j = x; j <= n; j++) {
                f[j] = Math.min(f[j], f[j - x] + 1); }}returnf[n]; }}Copy the code
  • Time complexity: N ∗nn * \ SQRT {n}n∗n states need to be transferred, and the complexity is O(n∗n)O(n * \ SQRT {n})O(n∗n).
  • Space complexity: O(n)O(n)O(n).

Backpack Problem (Table of Contents)

  1. Knapsack: Knapsack problem first lecture

    1. Lesson 2 (416. Segmentation and Subsets)

    2. Lesson 3 (416. Segmentation and Subsets)

  2. Complete knapsack: Lecture 4 of the knapsack problem

    1. Perfect Knapsack problem Lecture 5 (279. Perfect Squares)

    2. Lesson 6 (322. Small Change)

    3. Lesson 7 (518. Change FOR II)

  3. Multiple backpacks: Lecture 8 on the Backpack Problem

  4. Multiple backpacks

    1. Multiple Knapsacks: The Knapsack problem lecture 9

    2. Multiple Knapsacks: The Knapsack problem lecture 10

  5. Mixed backpack

    1. Mix the backpack

  6. Packet backpack

    1. 【 exercise 】 Pack in groups

  7. Multidimensional knapsack

    1. Lesson 1 (474. Ones and Zeros)
    2. Lecture * (879. Profit Planning)

  8. The tree backpack

    1. A tree backpack

  9. Knapsack solution number

    1. Lesson 1 (494. Goals and Sums)
    2. Lecture * (879. Profit Plan)

  10. Backpack for specific programs

    1. 【 典 型 范 例 】 Backpack: backpack problem first lecture (1049. The weight of the last stone II)

  11. Generalization backpack

    1. 【 exercise 】 Generalization backpack

The last

This is No.279 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.