ゼロから始める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: Right -> Right -> Down Ri