ゼロから始めるLeetCode Day89 「62. Unique Paths」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day88「139. Word Break」

次回
ゼロから始めるLeetCode Day90「1011. Capacity To Ship Packages Within D Days」

Twitterやってます。

問題

62. Unique Paths
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としてはユニークな経路の数を求める、というものです。
ロボットがm x nのグリッドの左上隅に位置しています（下図では「スタート」と表示されています）。

なお、ロボットはどの時点でも下か右にしか移動できません．ロボットはグリッドの右下隅に到達しようとしています（下図では「Finish」と表示されています）。

今回は図を載せないので、噛み砕いて考えたい方は直接問題のリンクで確認してください。

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

#解法

ユニークな経路の数を求める問題ですね。
こちらも前回同様Dynamic Programmingで解くのが非常に効果的な問題のタイプです。

ちなみに経路の求め方についてですが、説明はこちらの方が英語で超分かりやすく説明してくださっています。あまり馴染みがない方でも比較的理解がしやすいと思うので、初めてこういう問題を解く場合は見てみることをオススメします。

では解答です。

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.

なお、前半の

dp = [1]*n

以上のコードは別になくても回答は通ります。
が、どうしても例外が発生する可能性もあるので書いておくほうが無難でしょう。
事実discussの解答でも多くの人が書いていますし、仮にコーディング面接等だったら突っ込まれる可能性があると思いますし。

それから後のコードは基本的には先ほど紹介した動画で説明されていたことをそのままコードにした、という感じなのでそこまで説明が必要ではなさそうです。

ちなみにこの問題をYouTubeで検索するとAmazonで出題されたことがある、というような紹介のされ方をされているので、気になる方は調べてみると良いかもしれませんね。

では今回はここまで。お疲れ様でした。