chase freedom又有200的开卡offer# Money - 海外理财
O*i
1 楼
和一个美国人吧。给一个矩阵和一个数k，要算另外一个矩阵。新的矩阵的每个位置是
老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
实现这个算法。写了三个函数。
在火车上睡觉的时候想了个解法，不知道对不对。
这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
最小以及median, 其实也就是二维的离散拉普拉斯算符。
其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
求和。对一维数组A, 如果构造辅助数组B, 使得
B[j] = A[0] + A[1] + ... A[j]
则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
间求得，而不用O(k)。
构造B的过程是DP, 类似Fibonacci的DP构造。
扩展到二维也是一样的，二维数组B每个元素的值，是二维数组A的左上顶点元素到右下
和B那个元素位置对应元素的子矩阵的和。
构造B的过程也是DP, 只是递归方程比一维情形稍微复杂些，是两个矩阵相加，减去相
交部分矩阵，再加上右下顶点。利用B求A中任意子矩阵的和完全类似。画个图，利用简
单集合论知识就清楚了。
另外我觉得这题，就是CC 150上二维数组求最大子矩阵和的变体，都利用了辅助数组B。
所以说熟看CC 150还是很有必要的，不知道CAIWU有没有受CC 150那道题的影响？
老矩阵里面每个对应位置位中心边长为k的小矩阵的平均。用DP算法可以做到N^2。然后
实现这个算法。写了三个函数。
在火车上睡觉的时候想了个解法，不知道对不对。
这个题的背景实际上是二维数字图像处理的卷积滤波。这里是求平均，也可以求最大，
最小以及median, 其实也就是二维的离散拉普拉斯算符。
其实可以先考虑一维的情形。难点是如何用空间换时间，不需要每次都对k个数都重新
求和。对一维数组A, 如果构造辅助数组B, 使得
B[j] = A[0] + A[1] + ... A[j]
则A[m] + A[m + 1] + ... + A[m + k - 1] = B[m + k - 1] - B[m - 1]，可以O(1)时
间求得，而不用O(k)。
构造B的过程是DP, 类似Fibonacci的DP构造。
扩展到二维也是一样的，二维数组B每个元素的值，是二维数组A的左上顶点元素到右下
和B那个元素位置对应元素的子矩阵的和。
构造B的过程也是DP, 只是递归方程比一维情形稍微复杂些，是两个矩阵相加，减去相
交部分矩阵，再加上右下顶点。利用B求A中任意子矩阵的和完全类似。画个图，利用简
单集合论知识就清楚了。
另外我觉得这题，就是CC 150上二维数组求最大子矩阵和的变体，都利用了辅助数组B。
所以说熟看CC 150还是很有必要的，不知道CAIWU有没有受CC 150那道题的影响？
