スポンサーリンク

【LeetCode】62. Unique Paths 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約5分で読めます。

 

問題

原文

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

Example 2:

 

Constraints:

  • 1 <= m, n <= 100

 

内容

 

m×nグリッド上にロボットがあります。

はじめに、ロボットは左上の角(grid[0][0])にいます。

ロボットは右下の角(grid[-1][-1])に行こうとします。

ロボットは1回の移動で下か右にのみ移動できます。

整数m,nが与えられるので、ロボットが右下の角に行くための経路の数を返してください。

 

※正しくない可能性があります。

 

解答

解答1:Python, DP

 

動的計画法。

各番地への経路数を記録するためのの二次元配列dpを作成。

dp配列は各番地を見立てており、その中にその番地へ至るための経路数を記録する。

m,nのどちらかが1の場合、右下の角への経路は1になるのでその場合の処理を記述している。

また、0行目と0列は番兵のつもりだったので実際には不要なマス。

※番兵はfor文中で配列を参照した際、配列外参照を防ぐために余分に加えた行と列。

(1,2)番地と(2,1)番地を1でセット。これは初期位置から右、または下に移動したときの経路。

for文を2つ重ねて配列を処理する。

ある番地へ至るための経路数は、その左と上に隣接している番地へ至るための経路数の合計。

最初にdp配列を0で初期化してしまったため、もともとの配列の値に、左と上の番地の値を加える形で計算。

 

他の解答者が書いていた解答のコードはシンプルでわかりやすい。

 

 

解答2:Python, DP 2

 

 

DP配列を全て1で初期化する。また、m,nは+1をせずに配列を作成。

こうすることで解答1とは違ってm,nが2より小さい場合の処理をしなくても良い、

初期位置の右・下に移動したときに1をセットする必要もない。

解答3:Python, メモ化再帰

 

 

メモ化再帰。

リストや辞書などのシーケンス型の変数を使って、値を記録しながら再帰処理を行う。

今回は辞書型変数memoを準備し、再帰処理を行う関数の中で各番地への経路数を記録している。

初期位置(0,0)と(1,1)の場合は個別に処理を記述し、後は一般化された経路数の計算で対応できる。

これも他の方の解答。わかりやすい。

 

解答4で記載しているが、この解答では関数uniquePathsのmemoの中身は変わらない。

※関数uniquePathsの最後にmemoをprintしたら空の辞書が返ってきた。

ただし、path_countの中でmemoを使うので、uniquePathsでmemoを初期化しておく必要はある。

 

 

解答4:Pyton, メモ化再帰

 

 

解答3と全く同じロジック。

memoの中身を見たいがために色々いじった結果汚くなった。

関数uniquePathsではmemoを初期化しているが、単にuniquePathsの最後にprintしただけでは空の辞書が返ってきたことがきっかけ。

path_countの中でmemoには経路数が記録されるが、特にreturnされるわけでもないので、uniquePathsでのmemoは何も変わらない?

 

 

メモ・参考・感想

■感想

動的計画法(dynamic programming)

AtcoderのDPばかりを集めたコンテストにしか当たったことがなかった。

解答1は改善点だらけだけども、自分で解くことができたのは良い点だった。

 

■参考

・AtcoderのEDPC

Educational DP Contest / DP まとめコンテスト – AtCoder

 

・全然メモしていないけど、このサイト内での解答記録

EDPC記事一覧

 

 

 

前:45. Jump Game II

次:413. Arithmetic Slices

LeetCode 解答・解説記事一覧

コメント