#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/logarithms/perfect-squares-implementation-the-code

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/logarithms/perfect-squares-implementation-the-code

Repovive

Perfect Squares - Implementation (The code) - Logarithms | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Perfect Squares - Implementation (The code)

DP solution

Here's the dynamic programming solution:


function numSquares(n)
    dp := array of size (n + 1) filled with infinity
    dp[0] := 0
    for i from 1 to n
        j := 1
        while j * j ≤ i
            dp[i] := min(dp[i], dp[i - j * j] + 1)
            j := j + 1
    return dp[n]

You build up $dp$ from $0$ to $n$ . For each $i$ , you try all perfect squares $j^2 \leq i$ and take the minimum. The answer is $dp[n]$ .