矩阵中的最长子序列
Longest sub-sequence in a matrix
我有这样一个矩阵->
1 6 2
8 3 7
4 9 5
你可以走任何方向，从上到下从左到右对角线，你必须找到最长的子序列，你可以 select 序列中的下一个数字，其绝对差大于3.
像上面的例子一样，最长的子序列是1->6->2->7->3->8->4->9->5。
我可以为它编写一个蛮力代码，它可以找到最长的序列，就像找到第一个数字、第二个数字等的最长序列一样。 return 是计数最大的那个。
我是DP新手。有没有其他方法可以通过使用DP来解决这个问题？我无法理解使用 DP 的解决方案。
设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就可以了。
我有这样一个矩阵->
1 6 2
8 3 7
4 9 5
你可以走任何方向，从上到下从左到右对角线，你必须找到最长的子序列，你可以 select 序列中的下一个数字，其绝对差大于3.
像上面的例子一样，最长的子序列是1->6->2->7->3->8->4->9->5。
我可以为它编写一个蛮力代码，它可以找到最长的序列，就像找到第一个数字、第二个数字等的最长序列一样。 return 是计数最大的那个。
我是DP新手。有没有其他方法可以通过使用DP来解决这个问题？我无法理解使用 DP 的解决方案。
设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就可以了。