[PYTHON] Let Code Day89 "62. Unique Paths" Starting from Zero

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 Day 88 "139. Word Break" starting from zero

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

62. Unique Paths The difficulty level is Medium. This is an excerpt from Leet Code 60 Questions I Want to Solve for Coding Interview Preparation.

The problem is finding the number of unique routes. The robot is located in the upper left corner of the m x n grid (it is labeled" Start "in the figure below).

Note that the robot can only move down or to the right at any given time. The robot is about to reach the lower right corner of the grid (it is labeled "Finish" in the figure below).

I will not post a figure this time, so if you want to chew and think about it, please check directly with the link in question.

Example 1:

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3 Output: 28

solution

It's a matter of finding the number of unique routes. This is also a very effective type of problem to solve with Dynamic Programming as before.

By the way, regarding how to find the route, here explains in English in a super easy-to-understand manner. I think it's relatively easy to understand even for those who are not very familiar with it, so I recommend you to take a look when solving such a problem for the first time.

Then the answer.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        if n < m:
            self.uniquePaths(n,m)
        dp = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                dp[j] += dp[j-1]
        return dp[-1]
# Runtime: 28 ms, faster than 84.67% of Python3 online submissions for Unique Paths.
# Memory Usage: 13.8 MB, less than 74.12% of Python3 online submissions for Unique Paths.

In addition, in the first half

dp = [1]*n

The answer will pass even if you do not have the above code. However, it is safer to write it because exceptions may occur. In fact, many people write in the answer of discuss, and I think that if it is a coding interview etc., it may be rushed.

After that, the code after that is basically the same as the code explained in the video introduced earlier, so it seems that explanation is not necessary so much.

By the way, if you search for this problem on YouTube, it is introduced that you have been asked on Amazon, so if you are interested, you may want to check it.

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