Shulou(Shulou.com)06/01 Report--

This article mainly shows you "how to solve the problem of complete squares in leetcode". The content is simple and clear. I hope it can help you solve your doubts. Let me lead you to study and learn this article "how to solve the problem of complete squares in leetcode".

Topic link

Https://leetcode-cn.com/problems/perfect-squares/

Topic description

Given a positive integer n, find several complete square numbers (such as 1, 4, 9, 16,.) so that their sum is equal to n. You need to minimize the number of complete squares of the sum.

Example 1:

Input: n = 12

Output: 3

Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

The idea of solving the problem

Tags: dynamic plannin

First initialize the array dp of length 1, with each position 0

If n is 0, the result is 0

The array is traversed with the subscript I, and each time the current number is updated to the maximum result, that is, dp [I] = I, for example, iTunes 4. The worst result is 4 "1" 1 "1" 1, that is, 4 digits.

The dynamic transfer equation is as follows: dp [I] = MIN (dp [I], dp [I-j] + 1), I represents the current number, and Jedj represents the square.

Time complexity: O (n*sqrt (n)), sqrt is the square root

Code

Java version

Class Solution {

Public int numSquares (int n) {

Int [] dp = new int [n + 1]; / / default initialization values are all 0

For (int I = 1; I = 0; jacks +) {

Dp [I] = Math.min (dp [I], dp [I-j * j] + 1); / / dynamic transfer equation

}

}

Return dp [n]

}

}

JavaScript version

/ * *

* @ param {number} n

* @ return {number}

, /

Var numSquares = function (n) {

Const dp = [... Array (nail1)] .map (_ = > 0); / / the array length is nim1, and the values are all 0.

For (let I = 1; I = 0; jacks +) {

Dp [I] = Math.min (dp [I], dp [I-j * j] + 1); / / dynamic transfer equation

}

}

Return dp [n]

}

Drawing and interpretation

These are all the contents of the article "how to solve the problem of complete squares in leetcode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.