切矩阵

https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#

切矩阵

第四轮比较难，出了我不大擅长的dp，说给一个m x n的矩阵，可以横着切或者竖着切，每横着切一刀的cost为被切矩阵的列数的平方，每竖着切一刀的cost是被切矩阵的行数的平方。然后给一个desired area，问切到这个area大小最少的cost是多少。好像切好以后两个矩阵都能继续切，差点没做出来，还是弱鸡啊

输入为矩阵的长和宽和一个int代表desired area

思路：

dfs带memorization，一刀切成两半，在其中一半找面积为k的矩形，在另一半找面积为desired area - k的矩形，然后每一刀有两种切法，横着切，竖着切，分别遍历

code:

Provider: null

   Map<List<Integer>, Integer> memo = new HashMap<>();
   public int minCost(int rows, int cols, int area) {
    // sanity check
    return dfsUtil(rows, cols, area);
   }
   private int dfsUtil(int rows, int cols, int area) {
    if(area == 0) return 0;
    if(rows == 0) return 10000; // some big integer will mask the result in min() function
    if(cols == 0) return 10000;
    if(rows * cols == area) return 0;
    if(rows * cols < area) return 10000;
    if(memo.containsKey(Arrays.asList(rows, cols, area))) {
    return memo.get(Arrays.asList(rows, cols, area));
    }

    int cost = Integer.MAX_VALUE;
    for(int k = 0; k <= area; k++) {
    // cut row
    int tmp = (int) Math.pow(cols, 2);
    for(int i = 1 ; i <= rows / 2 ; i++) {
    cost = Math.min(cost, tmp + dfsUtil(i, cols, k) + dfsUtil(rows - i, cols, area - k));
    }
    // cut cols
    tmp = (int) Math.pow(rows, 2);
    for(int j = 1 ; j <= cols / 2; j++) {
    cost = Math.min(cost, tmp + dfsUtil(rows, j, k) + dfsUtil(rows, cols - j, area - k));
    }
    }
    memo.put(Arrays.asList(rows, cols, area), cost);
    return cost;
   }

这题需要用DFS搞分治法吗？给定一个面积，你可以枚举出所有的长*宽组合，对原矩阵，只要对某个长宽能切割，最多两刀就能把目标矩形切出来，只是先横切还是先竖切的代价可能不同罢了。可能我理解错了题意 （editor：最后想要的面积并不一定是一个规则的矩形）

这题切的具体含义可以解释的更清楚一点么？是必须平均分，还是按照整数切还是随意的位置切呢？