最长子序列

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。