最長のサブシーケンスが

Question

私はあなたがアップダウン右左斜め、どの方向に行くことができthis->

1 6 2 
8 3 7 
4 9 5 

のような行列があり、最長のサブシーケンスを見つける必要があり、あなたが選択することができますその絶対差が3より大きいような順序で次の番号を割り当てる。

上記の場合と同様に、最長サブシーケンスは1->6->2->7->3->8->4->9->5である。

私は最初の番号や2番目の番号などの最長シーケンスを見つけるような最長のシーケンスを見つけるためのブルートフォースコードを書くことができます。そして、最大のカウントを持つものを返します。

私はDPを初めて使用しています。 DPを使ってこれを解決する他の方法はありますか？私はDPを使って解決策を理解することができません。

Answer 1

Nを行数とし、Mを列数とします。

あなたが状態で、動的プログラミングアプローチを試すことができます。 dp(int row_idx, int col_idx, int visited_msk)visited_msk（すなわちmatrix[i][j]ためvisited_mskでIDがあなたのDPインサイドi*M + j

になり、今まで訪問した細胞を表す整数であり、あなたは意志隣接する8つのセル（境界内にある場合）を繰り返し、絶対差が3より大きく、次のようにセルが訪問されない場合にのみ現在のセルからDPを呼び出します。

マスクはnew_idx = new_row_idx * M + new_col_idxです内部ループで、次いで条件はこのようなものであろう：

if(abs(matrix[row_idx][col_idx] - matrix[new_row_idx][new_col_idx]) > 3 && !((visited_msk >> new_idx) & 1)) { 
    result = max(result, dp(new_row_idx, new_col_idx, visited_msk | (1<<new_idx)) + 1); 
} 

このアプローチの順序は、（2 ^（N * M）* N * M * 8）Oであり、それは微細になりN * M（グリッドサイズ）が< = 15の場合