java - 求矩阵中元素的最小和

Question

给定一个矩阵，找到元素的最小和，使得元素从每一行中选择，并且相邻元素不应来自同一列。假设矩阵只有 3 列。

example 1:
[[1, 2, 3], 

 [1, 2, 3], 

 [3, 3, 1]]

minimum sum = 1 + 2 + 1 = 4  // matrix[0][0] + matrix[1][1] + matrix[2][2] or matrix[0][1] + matrix[1][0] + matrix[2][2]

example 2:
[[1, 100, 1], 

 [2, 99, 30],

 [100, 12, 13]]

minimum sum = 1 + 2 + 12 = 15 // matrix[0][2] + matrix[1][0] + matrix[2][1]

example 3:
[[1, 2, 3], 

 [2, 5, 4],

 [2, 3, 1],

 [1, 6, 3]]

minimum sum = 2 + 2 + 1 + 1 = 6 // matrix[0][1] + matrix[1][0] + matrix[2][2] + matrix[3][0]

这是我的代码:

    public static int minCost(List<List<Integer>> matrix) {
        // Write your code here
        int rows = matrix.size();

        int[] cost = findMin(matrix.get(0), -1);
        int total = cost[0];

        for (int i = 1; i < rows; i++){
            List<Integer> row = matrix.get(i);
            cost = findMin(row, cost[1]);
            total += cost[0];
        }
        return total;
    }

    private static int[] findMin(List<Integer> row, int col){
        int[] ans = new int[2];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < row.size(); i++) {
            if (i == col){
                continue;
            }
            if (row.get(i) < min) {
                min = row.get(i);
                ans[0] = min;
                ans[1] = i;
            }
        }
        return ans;
    }

我最初用贪心法来处理这个问题，即找到一行中最小的元素，并且该元素的列与前一个元素不同。

此方法不满足示例 2 和示例 3。我认为动态编程是解决此问题的方法，但我不确定如何构造 mem 部分。如何用动态规划来实际解决这个问题？提前致谢!

Answer 1

是的，您需要识别您在评论之一中指定的递归结构。

您可以按如下方式识别:假设您当前位于行 row 上，并且您选择的前一列是 prevcol，那么您需要选择一个不在前一列中的值，并对剩余的值进行递归行并获取所有此类值的最小值，即每次选择不是前一列的列，并通过指定所选的前一列是您刚才选择的列来递归剩余行。

查看这个递归方程以了解更多信息:

f( arr, row, prevcol ) = 最小值(对于所有不等于 prevcol 的 col ( arr[row][col] + f( arr, row + 1, col ) )

您知道如何指定在调用中选择的下一行和上一列f(arr, row +1, col ) 吗？

基本条件是如果row == arr.length，即没有剩余行，则结果为0。

并且您可以记住 row 和 prevcol 的每个组合获得的值

Java 代码为:

private static int f( int[][] arr, int row, int prevCol ) {
    if ( row == arr.length ) return 0;

    int C = arr[row].length;
    if ( dp[row][prevCol+1] != Integer.MAX_VALUE ) return dp[row][prevCol+1];
    int res = Integer.MAX_VALUE;
    for ( int j = 0; j < C; j++ ) {
      if ( j != prevCol ) {
        int val = arr[row][j] + f ( arr, row + 1, j );
        res = Math.min ( res, val );
      }
    }
    dp[row][prevCol+1] = res;
    return res;
  }

您需要实例化 dp 数组，如下所示:

dp = new int[arr.length][arr[0].length+1];
for ( int[] r : dp ) Arrays.fill(r, Integer.MAX_VALUE);

你可以这样调用该函数:f( arr, 0, -1 ) 其中 0 是起始 行，-1 是 >prevcol。由于 prevcol 以 -1 开头，因此您需要将值存储在 dp[row][prevcol+1]

中

对于第三个示例，答案是 6 而不是 9。

row = 0, col = 1 : 2
row = 1, col = 0 : 2
row = 2, col = 2 : 1
row = 3, col = 0 : 1
2 + 2 + 1 + 1 = 6