この非常に一般的な DP 問題 (動的プログラミング) があるとします -
コスト行列 cost[][] と cost[][] 内の位置 (m, n) を指定して、(0, 0) から (m, n) に到達するための最小コスト パスのコストを返す関数を記述します。行列の各セルは、そのセルを通過するためのコストを表します。(m, n) に到達するパスの合計コストは、そのパス (送信元と宛先の両方を含む) のすべてのコストの合計です。特定のセル、つまり、特定のセル (i, j)、セル (i+1, j)、(i, j+1)、および (i+1, j+1) をたどることができます。すべてのコストが正の整数であると仮定できます。
PS: これに対する回答 - 8
さて、この問題を解いた後、次のような疑問が頭をよぎりました。
1000*1000 の行列があるとします。O(n^2) には時間がかかります (インテル i5 では確かに 1 秒未満)。しかし、さらに最小化できますか。このアルゴリズムを使用して 6 ～ 8 個のスレッドを開始し、それらを同期して最終的に答えを得るとしますか? 答えを得るのが速いか、論理的に可能か、それともこの考えを捨てるべきか