首先一个显然的思路就是dp
dp[i][j] 表示枚举到第i个点 当前恰好有j个合法的线段的方案数

init: dp[0][0] = 1
转移: dp[i][j] = dp[i - 1][j]; // 不选当前点
      dp[i][j] = dp[t][j - 1]; t = {1, i - 1} && j >= 1 // 选当前点
    时间复杂度：O(n ^ 3) tle
所以可以进行优化：
    我们发现每次都是从{1, i - 1}去求一个前缀和
    所以我们可以在推dp的时候就推前缀和每次先更新dp再更新s
    这样就行了吗？
    我们发现dp[i][j] 用到的都是i - 1状态
    所以我们对j要倒着枚举
    然后就可以愉快的AC啦!!!

tle代码

typedef long long LL;

const LL mod = 1e9 + 7;
const int N = 1000 + 10;

LL dp[N][N];

class Solution {
public:
    int numberOfSets(int n, int k) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(int i = 1;i <= n;i ++ ){
            for(int j = 0;j <= k;j ++ ){
                dp[i][j] = dp[i - 1][j] % mod;
                if(j < 1) continue;
                for(int t = 1;t < i;t ++ )
                    (dp[i][j] += dp[t][j - 1]) %= mod;
            }
        }

        return dp[n][k] % mod;
    }
};

前缀和优化代码

typedef long long LL;

const LL mod = 1e9 + 7;
const int N = 1000 + 10;

LL dp[N][N];
LL s[N];

class Solution {
public:
    int numberOfSets(int n, int k) {
        for(int i = 0;i <= n;i ++ )
            for(int j = 0;j <= k;j ++ )
                dp[i][j] = 0;
        for(int j = 0;j <= k;j ++ ) s[j] = 0;
        dp[0][0] = 1, s[0] = 0;
        for(int i = 1;i <= n;i ++ ){
            for(int j = k;j >= 0;j -- ){
                dp[i][j] = dp[i - 1][j];
                if(i >= 2 && j >= 1) (dp[i][j] += s[j - 1]) %= mod;
                (s[j] += dp[i][j]) %= mod;
            }
        }

        return dp[n][k] % mod;
    }
};