[PYTHON] Let Code Day69 starting from scratch "279. Perfect Squares"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day68 starting from zero "709. To Lower Case"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!

problem

279. Perfect Squares The difficulty level is Medium. Excerpt from Top 100 Liked Questions.

Given a positive integer n, the problem is to find the minimum number of perfect square numbers that add up to n (eg 1, 4, 9, 16, ...).

Example 1:

Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

solution

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n+1)]
        for i in range(2,n+1):
            for j in range(1,int(i ** 0.5)+1):
                dp[i] = min(dp[i],dp[i-j*j]+1)
        return dp[n]
# Runtime: 4608 ms, faster than 39.65% of Python3 online submissions for Perfect Squares.
# Memory Usage: 14 MB, less than 60.54% of Python3 online submissions for Perfect Squares.

Implemented using dynamic programming. When I saw the problem, it turned out to be DP. If the value is small, you can do a full search, but it is inefficient by any means, so I wrote it as above.

In addition, as a recommendation of dynamic programming of personal Qiita articles Super Introduction to Dynamic Programming! Educational DP Contest A to E Problem Explanations and Similar Issues And in the implementation in Python Dynamic Programming (DP) Learning Memo ~ by Python ~ Part 1

Isn't it a good example? I think it's better to grasp the concept in the former and learn about the implementation in Python in the latter.

By the way, it's strange that it's Dynamic Programming in English, though it's Dynamic Programming in Japanese.

So that's it for this time. Thank you for your hard work.