我正在寻找一个算法,可以帮助我在一个二维数组中找到非相邻元素的最大和。
对于一维数组,我已经从以下链接中找到了有用的解决方案:
1) http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/ 2) https://www.youtube.com/watch?v=UtGtF6nc35g例如,在一个一维数组 {3, 2, 6, 2, 10} 中,我将得到最大和为19,因为3、6和10是非相邻的。
然而,我无法找到一个可以帮助我处理二维数组的算法。如何在这个数组中找到不包含水平或垂直相邻元素的整数的最大总和?对角线相邻的元素是允许的。
例如:
[3, 2, 6, 2, 10]
[1, 5, 2, 5, 1]
[5, 1, 7, 2, 9]
[3, 9, 1, 8, 2]
是否有现有算法来解决这个问题?如果我使用另一种数据结构而不是2D数组,是否会有另一种方法来解决这个问题?