假设我在
Java中有一个m x n矩阵.
我想从第一列到最后一列找到最大遍历代价.每个值代表所产生的成本.我被允许沿着矩阵上,下,右方向行进.每个单元格只能访问一次.允许从列的顶部单元到底部的转换,反之亦然.
为了简单起见,请考虑以下矩阵：
- 2 3 17
- 4 1 -1
- 5 0 14
如果我应该找到最大成本,我的答案是46(2→5→4→1→3→0→14→17).
- maxCost(of destination node) = max{ maxCost(at neighbouring node 1),maxCost(at neighbouring node 2),maxCost(at neighbouring node 3) } + cost(of destination node)
在这种情况下,它会像：
- maxCost(17) = max{ maxCost(3),maxCost(-1),maxCost(14) } + 17;
因为每个单元格被允许被访问一次,所以我明白我需要维护一个相应的m×n isVisiting矩阵.但是,我不知道如何维护isVisiting矩阵.当计算maxCost(3)时,矩阵将被修改;但是对于maxCost(-1)和maxCost(14),我将需要其初始状态(将丢失).
解决方法
这是一个艰难的一个.请注意,由于您的路径不能重复访问的细胞,您的可能的路径将具有“蛇”的行为,例如：
这个想法是在f [j] [i]中存储在单元格(j,i)上结束的路径的最大长度.现在让我们说,我们要从f [j] [i-1]转换到f [j’] [i].那么我们可以直接选择从单元格(j,i)到单元格(j’,i),或者我们可以从单元格(j,i)边缘边缘因此,f [j] [i]的更新可以计算为：
哪里
这里a是给定的数组.
现在的问题是如何有效地计算sum(a [j..j’] [i],否则运行时将为O(m ^ 3n),您可以通过使用临时变量tmp_sum来求解(a [ j.j’] [i]),当你增加j时,你会递增.算法的运算符将是O(m ^ 2 n).
以下是一个示例实现：
- package stackoverflow;
- public class Solver {
- int m,n;
- int[][] a,f;
- public Solver(int[][] a) {
- this.m = a.length;
- this.n = a[0].length;
- this.a = a;
- }
- void solve(int row) {
- f = new int[m][n];
- for (int i = 0; i < m; ++i)
- for (int j = 0; j < n; ++j)
- f[i][j] = Integer.MIN_VALUE;
- for (int i = 0; i < n; ++i) {
- int sum = 0;
- for (int j = 0; j < m; ++j)
- sum += a[j][i];
- for (int j1 = 0; j1 < m; ++j1) {
- int tmp_sum = 0;
- boolean first = true;
- for (int j2 = j1; j2 != j1 || first; j2 = (j2+1)%m) {
- if (first)
- first = false;
- tmp_sum += a[j2][i];
- int best_sum = Math.max(tmp_sum,sum - tmp_sum +a[j1][i]+a[j2][i]);
- if (j1 == j2)
- best_sum = a[j1][i];
- int prev = 0;
- if (i > 0)
- prev = f[j1][i-1];
- f[j2][i] = Math.max(f[j2][i],best_sum + prev);
- }
- }
- }
- System.out.println(f[row][n-1]);
- }
- public static void main(String[] args) {
- new Solver(new int[][]{{2,3,17},{4,1,-1},{5,14}}).solve(0); //46
- new Solver(new int[][]{{1,1},{-1,-1}}).solve(0); //2
- }
- }
