<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 n;
    const int mod = 1e9+7;
    long long int dp[1005][1005][2];
    
    // startHere = 1, means we can start to draw a line from here 
    // startHere = 0, means line is continuing we can choose to stop 
    //                and start a new from this very point
    
    // i pts,  k segments
    int go(int i, int k, int startHere) {
        // Found a way to draw k valid segments
        if(k == 0)    return 1;
        
        // Reach end of points
        if(i == n)    return 0; 
        
        ////// Option 1: Skip this point
        // if startHere = 1, if we skip, we choose not to draw a line
        // if startHere = 0, if we skip, we choose to continue this line 
        //                   without marking and end point here
        long long int &ans = dp[i][k][startHere];
        if(ans != -1)    return ans; 
        
        ans = go(i+1, k, startHere);
        
        ////// Option 2: Take ith point
        if(startHere == 1) {
            // Take ith point as start
            // start the line 
            ans += go(i+1, k, 0);
            // we do not reduce k, we will decrement it when we find the end point of this line
        } else {
            // Take ith point as end
            // end the line here at (i), decrement k, 
            // since we can start a new line again from here at (i), so
            ans += go(i, k-1, 1);
        }
        
        ans %= mod;
        return ans;
    }
    
    int numberOfSets(int n, int k) {
        this->n = n;
        memset(dp, -1, sizeof(dp));
        return go(0, k, 1);
    }
};




// class Solution {
// public:
//     int numberOfSets(int n, int K) {
//         vector<vector<int>> dp(n, vector<int>(K + 1));
//         int kMod = 1e9 + 7;
        
//         dp[1][1] = 1; // 2 points, 1 segment
        
//         for (int i = 2; i < n; i++)
//             dp[i][1] = (i + 1) * i / 2; // 3 to n points, 1 segment
        
//         vector<vector<int>> sum(n, vector<int>(K + 1));
        
//         for (int i = 2; i < n; i++) {
//             for (int k = 2; k <= K; k++) {
//                 if (k <= i)
//                     sum[i][k] =  (sum[i - 1][k] + dp[i - 1][k - 1]) % kMod;
//                 dp[i][k] = (sum[i][k] + dp[i - 1][k]) % kMod;         
//             }
//         }
//         return dp[n - 1][K];
//     }
// };


// // dp[i][k]: num of ways to generate k non-overlapping segments you can make using [0~ i].

// // Then it's easy to see the transition as:
// // dp[i][k] = sum(dp[j][k-1]) + dp[i - 1][k], where j = k - 1 ~ i - 1
// // The first part of summation means: we make [j ~ i] as one segment and then check what's number of ways to generate k - 1 segs using [0 ~ j]. Second part means: we don't use i at all, so just check using [0 ~ i - 1], number of ways to generate k segs.

// // we need to get rid of this summation part which is the source of extra O(n). One can see that this summation is just another prefix sum - which we can easily get rid of with another "DP" approach:







25400