青训营刷题笔记17

问题描述

小M有一个 n×mn×m 的矩形蛋糕，蛋糕被分为 n×mn×m 个区域，每个区域都有一个美味度。她希望通过一刀将蛋糕切成两部分，一部分自己吃，另一部分给小团。切下的区域必须是完整的，即不能把某个小正方形切成两个小区域。

小M希望两个人吃的部分的美味度之和尽量接近。你的任务是计算出美味度差的最小值，即 ∣s1−s2∣∣s1​−s2​∣ 的最小值，其中 s1s1​ 是小M吃到的美味度，s2s2​ 是小团吃到的美味度。

测试样例

样例1：

输入：n = 2, m = 3, a = [[1, 1, 4], [5, 1, 4]]
输出：0

样例2：

输入：n = 3, m = 3, a = [[3, 2, 1], [4, 5, 6], [7, 8, 9]]
输出：3

样例3：

输入：n = 2, m = 2, a = [[1, 2], [3, 4]]
输出：2

问题分析

1. 输入：一个 n × m 的矩阵，其中每个元素表示对应位置的美味度。
2. 输出：我们需要返回通过切割得到的美味度差的最小值。

关键点：

• 切割方式：题目并未指定只能是水平切割或垂直切割，因此我们可以考虑两种方式：

  1. 水平切割：将矩阵分为上下两部分。
  2. 垂直切割：将矩阵分为左右两部分。

• 美味度计算：美味度差是我们需要最小化的目标，即：

  ∣s1−s2∣∣s1​−s2​∣

  其中，s_1 和 s_2 分别是上/左部分和下/右部分的美味度之和。

解题思路

1. 计算总美味度：首先，计算整个矩阵的美味度和 total_sum，这样我们可以方便地通过切割来计算每一部分的美味度。

2. 尝试所有可能的切割方式：

   • 对于水平切割，我们可以依次尝试每一行，将上方的部分和下方的部分分别作为两部分，计算它们的美味度差。
   • 对于垂直切割，我们可以依次尝试每一列，将左边的部分和右边的部分分别作为两部分，计算它们的美味度差。

3. 优化方案：

   • 对于每种切割方式，可以通过前缀和数组来加速计算每一部分的和。
   • 对于水平切割，可以利用每一行的美味度和来动态计算上方部分和下方部分的和。
   • 对于垂直切割，可以利用每一列的美味度和来动态计算左边部分和右边部分的和。

代码实现：

代码解释：

1. 计算总美味度：

   • 遍历整个矩阵，计算所有元素的和 total_sum，以便后续通过切割来计算两个部分的美味度之和。

2. 水平切割：

   • 对于每一行，计算其美味度和存储在 row_sum 中。
   • 通过逐步累加上方部分的和 sum_top，并计算下方部分的和 sum_bottom，然后更新最小美味度差。

3. 垂直切割：

   • 对于每一列，计算其美味度和存储在 col_sum 中。
   • 通过逐步累加左边部分的和 sum_left，并计算右边部分的和 sum_right，然后更新最小美味度差。

时间复杂度：

• 时间复杂度：O(n * m)，因为我们需要遍历整个矩阵来计算总美味度和每行/列的和，且每次切割的操作是线性计算的。
• 空间复杂度：O(n + m)，用于存储每一行和每一列的和。