最長子序列

Question

我喜歡這個 - >

1 6 2 
8 3 7 
4 9 5 

矩陣你可以去任何方向，上下左，右斜，你必須找到最長子序列，您可以選擇下一個數字，其絕對差值大於3.

像上述情況一樣，最長的子序列是1->6->2->7->3->8->4->9->5。

我可以寫一個暴力代碼，它找到最長的序列，就像找到第一個數字，第二個數字等等的最長序列一樣。並返回具有最大計數的那個。

我是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將i*M + j

你的DP裏面，你會迭代相鄰的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); 
} 

這種方法的順序是O（2 ^（N * M）* N * M * 8），所以這將是細如果N * M（網格大小）是< = 15。