<p>You are given an <code>m x n</code> integer matrix <code>mat</code> and an integer <code>target</code>.</p>

<p>Choose one integer from <strong>each row</strong> in the matrix such that the <strong>absolute difference</strong> between <code>target</code> and the <strong>sum</strong> of the chosen elements is <strong>minimized</strong>.</p>

<p>Return <em>the <strong>minimum absolute difference</strong></em>.</p>

<p>The <strong>absolute difference</strong> between two numbers <code>a</code> and <code>b</code> is the absolute value of <code>a - b</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1.png" style="width: 181px; height: 181px;" />
<pre>
<strong>Input:</strong> mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
<strong>Output:</strong> 0
<strong>Explanation:</strong> One possible choice is to:
- Choose 1 from the first row.
- Choose 5 from the second row.
- Choose 7 from the third row.
The sum of the chosen elements is 13, which equals the target, so the absolute difference is 0.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1-1.png" style="width: 61px; height: 181px;" />
<pre>
<strong>Input:</strong> mat = [[1],[2],[3]], target = 100
<strong>Output:</strong> 94
<strong>Explanation:</strong> The best possible choice is to:
- Choose 1 from the first row.
- Choose 2 from the second row.
- Choose 3 from the third row.
The sum of the chosen elements is 6, and the absolute difference is 94.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/matrix1-3.png" style="width: 301px; height: 61px;" />
<pre>
<strong>Input:</strong> mat = [[1,2,9,8,7]], target = 6
<strong>Output:</strong> 1
<strong>Explanation:</strong> The best choice is to choose 7 from the first row.
The absolute difference is 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 70</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 70</code></li>
	<li><code>1 &lt;= target &lt;= 800</code></li>
</ul>

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        M = len(mat)
        N = len(mat[0])
        cum_sum_set = set()
        for c in range(N):
            cum_sum_set.add(mat[0][c])
        for r in range(1,M):
            new_cum_sum_set = set()
            for c in range(N):
                for cum_sum in cum_sum_set:
                    # print(f"cum_sum={cum_sum} mat[r][c]={mat[r][c]} target-(M-r-1)={target-(M-r-1)}")
                    # if mat[r][c] + cum_sum <= target-(M-r-1):
                    new_cum_sum_set.add(mat[r][c] + cum_sum)
            cum_sum_set = new_cum_sum_set
        min_diff = -1
        for cum_sum in cum_sum_set:
            if min_diff == -1 or abs(cum_sum-target) < min_diff:
                min_diff = abs(cum_sum-target)
        return min_diff

        # '''
        # dp[r][c] := sum of elements from each row up to r that results in min absolute diff between target and mat[:r+1] if mat[r][c] is chosen
        # dp[r][c] = dp[r-1][c'] + mat[r][c] where c' is the optimal column that minimizes the absolute diff
        # O(m * n^2)
        # '''
        # M = len(mat)
        # N = len(mat[0])
        # dp = [[-1 for _ in range(N)] for _ in range(M)]
        # for c in range(N):
        #     dp[0][c] = mat[0][c]
        # for r in range(1,M):
        #     for c in range(N):
        #         for prev_c in range(N):
        #             if dp[r][c] == -1 or abs(dp[r-1][prev_c] + mat[r][c] - target) < abs(dp[r][c] - target):
        #                 dp[r][c] = dp[r-1][prev_c] + mat[r][c]
        
        # print(dp)
        # min_abs_diff = -1
        # for c in range(N):
        #     if min_abs_diff == -1 or abs(dp[M-1][c]-target) < min_abs_diff:
        #         min_abs_diff = abs(dp[M-1][c]-target)
        # return min_abs_diff
5901