Optimal Matrix Partition for Minimum Cost - DP Matrix Interview

Problem Given an N x M matrix of non-negative integers, partition it into exactly k non-overlapping horizontal strips (contiguous row groups). The cost of a strip is the sum of all elements in it. Minimize the maximum strip cost. Example: Approach Binary search on the answer: for a given max cost mid, greedily check if the matrix can be partitioned into at most k strips where each strip sum <= mid. Precompute row sums. Follow-ups What is the time complexity of the binary search + greedy check ap…