長方形のグリッドで最短のパスをコーナーにコーナー

私は解決できなかったインタビューのためにこの質問に出くわしました。 mxnグリッドのボトム左から右上コーナーまでの最短パスの数を計算するコード。これを解決するには？長方形のグリッドで最短のパスをコーナーにコーナー

2012-02-10 devnull

http://stackoverflow.com/questions/9105699/algorithm-for-finding-all-paths-in -a-nxn-grid http://stackoverflow.com/questions/9172053/all-possible-moves-in-a-5x5-grid http://stackoverflow.com/questions/9051254/finding-points-in -a-grid-with-exactly-k-paths-to-them 2週間以内に少なくとも3つの同じ質問がありました。検索を使用しようとしましたか？ – OleGG

https://en.wikipedia.org/wiki/Dynamic_programming

https://en.wikipedia.org/wiki/Memoization

出典

2012-02-10 02:08:27 ivancho

この回答は、インタビュアーが「あなたはどのように[x]を解決しますか？」という質問に私を困惑させようとしたときに私の「行きたい」という答えを思い出させます。私の返答：「数学*で」 –

このようなインタビューの質問の唯一のポイントは、あなたが動的プログラミングに精通しているかどうかを確認することです。私はここで魚を釣る人を教えています。 – ivancho

@ivancho：この特定の問題を解決するために動的プログラミングを使用する必要はまったくなく、解決策はO（1）の時間と空間で見つけることができます。ヒント：最短パスの長さは 'm + n 'なので、*任意の*最短パスには*正確に' m'水平と 'n'垂直ステップがあります。しかし、その順序は任意です。 –

ソリューションあなたはそれを解決したいと仮定すると、ではない：考える1x1の、1x2の、（M-1）×（n-1）の

出典

2012-02-10 02:12:15

この問題はAですthis questionのプライベートケースは、右上隅のすべてのパスにのみ自分自身を制限します。

簡略化のため、n * n行列[m * nに一般化することができます。他の1つのコーナーから各パスはexcactly2nそれらのうち移動し、持ってい
注 - 正確にn動きは、「アップ」であり、残りは「右」だから、

、あなたはすべてのあなたのパスを表すことができますバイナリーベクター、このようなバイナリーベクターの数が近い式O(1)でを用いて計算することができる1

に設定正確nビットの長さ2nの：choose(2n,n)。

n * m行列に一般化する：1つのコーナーからもう1つのコーナーまでの経路にいくつのステップがありますか？どれくらい "正しい"ものなのでしょうか？新しい行列に選択式を含めるようにして、前回と同じ結果が得られることを確認してください。n=m

出典

2012-02-10 07:54:28 amit

長方形のグリッドで最短のパスをコーナーにコーナー

答えて

関連する問題