<p>Given an <code>n x n</code> integer matrix <code>grid</code>, return <em>the minimum sum of a <strong>falling path with non-zero shifts</strong></em>.</p>

<p>A <strong>falling path with non-zero shifts</strong> is a choice of exactly one element from each row of <code>grid</code> such that no two elements chosen in adjacent rows are in the same column.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/falling-grid.jpg" style="width: 244px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6],[7,8,9]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is&nbsp;[1,5,7], so the answer is&nbsp;13.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[7]]
<strong>Output:</strong> 7
</pre>

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

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>-99 &lt;= grid[i][j] &lt;= 99</code></li>
</ul>

class Solution {
public:

    class RowMin
    {
    private:
        int m_capacity;
        int m_count;
        int* min;
        int* minIndex;
    
    public:
        RowMin(int capacity) : m_count(0), m_capacity(capacity) {
            min = new int[capacity];
            minIndex = new int[capacity];
        }

        RowMin() : RowMin(2) {}

        ~RowMin() {
            delete[] min;
            delete[] minIndex;
        }

        int get_min() {return m_count > 0 ? min[0] : INT_MAX;}

        int get_min_except_for_index(int index1)
        {
            for (int i = 0; i < m_count; i++)
            {
                if (minIndex[i] != index1)
                {
                    return min[i];
                }
            }
            return INT_MAX;
        }

        bool update(int index, int val)
        {
            bool expanded = false;
            if (m_count < m_capacity) {
                min[m_count] = val;
                minIndex[m_count] = index;
                m_count++;
                expanded = true;
            }
            for (int i = 0; i < m_count; i++)
            {
                if (val < min[i]) {
                    for (int j = m_count - 1; j > i; j--)
                    {
                        min[j] = min[j - 1];
                        minIndex[j] = minIndex[j - 1];
                    }
                    min[i] = val;
                    minIndex[i] = index;
                    return true;
                }
            }
            return expanded;
        }

    };

    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int** dp = new int*[n];
        for (int i = 0; i < n; i++)
        {
            dp[i] = new int[n];
        }

        RowMin* rowsMin = new RowMin[n];

        for (int j = 0; j < n; j++)
        {
            dp[n - 1][j] = grid[n - 1][j];
            rowsMin[n - 1].update(j, dp[n - 1][j]);
        }

        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = 0; j < n; j++)
            {
                int val = grid[i][j];
                int min = val + rowsMin[i + 1].get_min_except_for_index(j);
                dp[i][j] = min;
                rowsMin[i].update(j, min);
                // cout << i << " : " << j << " : " << dp[i][j] << endl;
            }
        }
        
        return rowsMin[0].get_min();
    }
};

/*

[[-73, 61, 43,-48,-36],  0
 [  3, 30, 27, 57, 10],  1
 [ 96,-76, 84, 59,-15],  2
 [  5,-49, 76, 31, -7],  3
 [ 97, 91, 61,-46, 67]]  4

*/
18700