問題
原文
There is a robot on an
m x ngrid. 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
mandn, 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution: def uniquePaths(self, m: int, n: int) -> int: #dp配列を0で初期化。m,nを+1しているのは番兵のつもりだった。 dp = [[0 for i in range(n+1)] for j in range(m+1)] #1行もしくは1列のみの場合、経路は1つしかない if m<2 or n <2: return 1 #(1,2)、(2,1)番地に1をセット。初期位置から右・下への移動は1通りのみ dp[1][2] = 1 dp[2][1] = 1 #dp配列の各番地への経路の数を順に計算する for row in range(1,m+1): for column in range(1,n+1): #ある番地への経路数は、左と上に隣接している番地への経路数の合計 dp[row][column] += dp[row-1][column] + dp[row][column-1] #右下の番地の値を返す return dp[-1][-1] |
動的計画法。
各番地への経路数を記録するためのの二次元配列dpを作成。
dp配列は各番地を見立てており、その中にその番地へ至るための経路数を記録する。
m,nのどちらかが1の場合、右下の角への経路は1になるのでその場合の処理を記述している。
また、0行目と0列は番兵のつもりだったので実際には不要なマス。
※番兵はfor文中で配列を参照した際、配列外参照を防ぐために余分に加えた行と列。
(1,2)番地と(2,1)番地を1でセット。これは初期位置から右、または下に移動したときの経路。
for文を2つ重ねて配列を処理する。
ある番地へ至るための経路数は、その左と上に隣接している番地へ至るための経路数の合計。
最初にdp配列を0で初期化してしまったため、もともとの配列の値に、左と上の番地の値を加える形で計算。
他の解答者が書いていた解答のコードはシンプルでわかりやすい。
解答2:Python, DP 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def uniquePaths(self, m: int, n: int) -> int: #dp配列を1で初期化 dp = [ [ 1 for j in range(n)] for i in range(m) ] #1からスタートすれば番兵は不要 for i in range(1, m): for j in range(1, n): #i,j番地は左と上の番地の合計値。 #for文は1からスタートしないと1行目か1列目でリストの範囲外参照になる dp[i][j] = dp[i][j-1] + dp[i-1][j] #リストの右下端の要素を返す return dp[m-1][n-1] |
DP配列を全て1で初期化する。また、m,nは+1をせずに配列を作成。
こうすることで解答1とは違ってm,nが2より小さい場合の処理をしなくても良い、
初期位置の右・下に移動したときに1をセットする必要もない。
解答3：Python, メモ化再帰
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution: def uniquePaths(self, m: int, n: int) -> int: #辞書型変数memo、番地とそこに至る道筋の数を記録 memo = {} def path_count(m, n): #既にメモされている場合はその値を返す if (m, n) in memo: return memo[(m, n)] #初期位置の場合はmemoに0を記録 if m == 0 or n == 0: memo[(m, n)] = 0 return 0 #1,1の場合は1を返す if m == 1 and n == 1: memo[(m, n)] = 1 return 1 #初期位置以外での計算。DPでも二重for文の中で同じ計算をする memo[(m, n)] = path_count(m-1, n) + path_count(m, n-1) #print(memo) return memo[(m, n)] #print(memo) ※memoはpath_count内でのみ変更されるのでuniquePath内では空のまま #右下端の値を返す return path_count(m, n) |
メモ化再帰。
リストや辞書などのシーケンス型の変数を使って、値を記録しながら再帰処理を行う。
今回は辞書型変数memoを準備し、再帰処理を行う関数の中で各番地への経路数を記録している。
初期位置(0,0)と(1,1)の場合は個別に処理を記述し、後は一般化された経路数の計算で対応できる。
これも他の方の解答。わかりやすい。
解答4で記載しているが、この解答では関数uniquePathsのmemoの中身は変わらない。
※関数uniquePathsの最後にmemoをprintしたら空の辞書が返ってきた。
ただし、path_countの中でmemoを使うので、uniquePathsでmemoを初期化しておく必要はある。
解答4：Pyton, メモ化再帰
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Solution: def uniquePaths(self, m: int, n: int) -> int: #辞書型変数memo、番地とそこに至る道筋の数を記録 memo = {} def path_count(m, n, memo): #既にメモされている場合はその値を返す if (m, n) in memo: return (memo[(m, n)],memo) #初期位置の場合はmemoに0を記録 if m == 0 or n == 0: memo[(m, n)] = 0 return (0, memo) #1,1の場合は1を返す if m == 1 and n == 1: memo[(m, n)] = 1 return (1, memo) #初期位置以外での計算。DPでも二重for文の中で同じ計算をする memo[(m, n)] = path_count(m-1, n, memo)[0] + path_count(m, n-1, memo)[0] #print(memo) return (memo[(m, n)], memo) #メモ化再帰処理の中でのみ記録されていたmemoを出力しようとしたらこうなった。 print(path_count(m, n, memo)[1]) #右下端の値を返す return path_count(m, n, memo)[0] |
解答3と全く同じロジック。
memoの中身を見たいがために色々いじった結果汚くなった。
関数uniquePathsではmemoを初期化しているが、単にuniquePathsの最後にprintしただけでは空の辞書が返ってきたことがきっかけ。
path_countの中でmemoには経路数が記録されるが、特にreturnされるわけでもないので、uniquePathsでのmemoは何も変わらない？
メモ・参考・感想
■感想
動的計画法(dynamic programming)
AtcoderのDPばかりを集めたコンテストにしか当たったことがなかった。
解答1は改善点だらけだけども、自分で解くことができたのは良い点だった。
■参考
・AtcoderのEDPC
Educational DP Contest / DP まとめコンテスト – AtCoder
・全然メモしていないけど、このサイト内での解答記録
コメント