0

2D座標プレーンでポイント1からポイント2に到達するためのユニークな方法の数を見つけるように求められた質問に出くわしました。

注：これは、一般性を失うことなく想定できx1 < x2ますy1 < y2。

さらに、モーションは次のように制限されます。右または上にしか移動できません。有効な移動がから(xa, ya)if(xb, yb)およびxa < xb。であることを意味しますya < yb。

数学的には、これはによって見つけることができます( [(x2-x1)+(y2-y1)]! ) / [(x2-x1)!] * [(y2-y1)!]。私もコードについて考えました。

動的計画法でコーディングしたアプローチがあり、アプローチにはO([max(x2,y2)]^2)時間がかかりTheta( x2 * y2 )、上三角行列または下三角行列で管理できます。

実行時間がこれより短い他のアプローチを考えられますか？最小実行時間がである再帰的ソリューションを考えていますO(max(x2,y2))。

4

4 に答える 4

1

単純で効率的な解決策は数​​学的な解決策です。

x2-x1 = nとしましょうy2-y1 = m。
あなたは正確nに右にステップを踏む必要があります、そしてmステップアップしてください、すべては彼らの順序を決定するために残されています。

n+mこれは、要素が1に正確にn設定された 要素を持つバイナリベクトルの数としてモデル化できます。
したがって、可能性の総数はchose(n,n+m) = (n+m)! / (n! * m!)、まさにあなたが得たものです。

数学的な答えが証明されており、計算が高速であることを考えると、これらの制限がある別のソリューションを使用する理由はわかりません。

ここで再帰を使用したい場合は、二項係数の再帰式がおそらくここに適しています。

編集：あなたはそれを計算するための乗法式を 探しているかもしれません。

于 2012-06-13T14:56:12.493 に答える
0

私は最終的に、この質問を詳細に説明し、回答を完成させる記事を書くことができました. これは同じリンクです。http://techieme.in/dynamic-programming-distinct-paths-between-two-points/

于 2013-08-11T18:56:01.250 に答える
0

答えを計算するには、次の式を使用できます。

(n+m)!/(n!m!)=(n+1)*(n+2)/2*(n+3)/3*…*(n+m)/m

したがって、擬似コードは次のとおりです。

let foo(n,m) =
  ans=1;
  for i = 1 to m do
    ans = ans*(n+i)/i;
  done;
  ans

乗算と除算の順序は重要です。変更すると、結果がそれほど大きくなくてもオーバーフローが発生する可能性があります。

于 2012-06-13T18:41:00.867 に答える