查找矩阵中元素的最小总和

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;
    }

我最初是用Greedy来接近这道题的，就是找一行中最小的元素，并且该元素的列与前一个元素的列不同。

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

Answer 1

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

您可以识别如下：假设您当前在一行 row 上，而您选择的上一列是 prevcol 那么您需要选择一个不在上一列中的值并递归其余行并获得最小值所有这些值，即每次您选择一个不是前一列的列并通过指定选择的上一列是您刚才选择的列来递归剩余的行。

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

f( arr, row, prevcol ) = minimum of ( for all col not equal to prevcol ( 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 是起始 row，-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

Answer 2

非常感谢@SomeDude 这是我的 python 实现相同的..

import math
def mincost(arr,row,prevcol,n,k):
    if row == len(arr):
        return 0
    C = len(arr[row])
    dp = [[math.inf for x in range(k+1)] for y in range(n)]
    if dp[row][prevcol+1] != math.inf:
        return dp[row][prevcol+1]
    res = math.inf
    for j in range(C):
        if j != prevcol:
            val = arr[row][j] + mincost(arr,row+1,j,n,k)
            res = min(res,val)
    dp[row][prevcol+1] = res
    return res

我检查了@bonus 指定的所有上述测试用例，它有效。

查找矩阵中元素的最小总和

Find minimum sum of elements in a matrix

java

algorithm

matrix

dynamic-programming

minimization