<p>Given <code>n</code> points on a 1-D plane, where the <code>i<sup>th</sup></code> point (from <code>0</code> to <code>n-1</code>) is at <code>x = i</code>, find the number of ways we can draw <strong>exactly</strong> <code>k</code> <strong>non-overlapping</strong> line segments such that each segment covers two or more points. The endpoints of each segment must have <strong>integral coordinates</strong>. The <code>k</code> line segments <strong>do not</strong> have to cover all <code>n</code> points, and they are <strong>allowed</strong> to share endpoints.</p>

<p>Return <em>the number of ways we can draw </em><code>k</code><em> non-overlapping line segments</em><em>.</em> Since this number can be huge, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/07/ex1.png" style="width: 179px; height: 222px;" />
<pre>
<strong>Input:</strong> n = 4, k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.
</pre>

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

<pre>
<strong>Input:</strong> n = 3, k = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.
</pre>

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

<pre>
<strong>Input:</strong> n = 30, k = 7
<strong>Output:</strong> 796297179
<strong>Explanation:</strong> The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10<sup>9</sup> + 7 gives us 796297179.
</pre>

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

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= n-1</code></li>
</ul>

class Solution {
public:
    int mod = 1e9 + 7;
    vector<vector<int>>dp;
    int FindWays(int i, int n, int k)
    {
        if(k == 0)return 1;
        if(i >= n)return 0;
        if(dp[i][k] != -1)return dp[i][k];
        int ans = FindWays(i + 1, n, k);
        for(int nxt = i + 1; nxt < n; nxt++)
        {
            ans = (ans + FindWays(nxt, n, k - 1)) % mod;
        }
        return dp[i][k] = ans;
    }
    int numberOfSets(int n, int k) {
        // dp.resize(n + 1, vector<int>(k + 1, -1));
        vector<long long int>prev(n + 1, 1);
        vector<long long int>suff_prev(n + 1, 0);
        int sum = 0;
        for(int i = n - 1; i >= 0; i--)
        {
            sum += prev[i];
            sum %= mod;
            suff_prev[i] = sum;

        }
        for(int kk = 1; kk <= k; kk++)
        {
            vector<long long int>ndp(n + 1, 0);
            for(int i = n - 1; i >= 0; i--)
            {
                ndp[i] += ndp[i + 1];
                ndp[i] %= mod;
                //ndp[i] += prev[i + 1] + .. prev[n - 1]
                ndp[i] += suff_prev[i + 1];
                // for(int nxt = i + 1; nxt < n; nxt++)
                // {
                //     ndp[i] = (ndp[i] + prev[nxt])%mod;
                // }
                ndp[i] %= mod;
            }
            prev = ndp;
            sum = 0;
            for(int i = n - 1; i >= 0; i--)
            {
                sum += prev[i];
                sum %= mod;
                suff_prev[i] = sum;
            }

        }
        // int ans = FindWays(0, n, k);
        return prev[0];
    }
};
50200