1621.Number-of-Sets-of-K-Non-Overlapping-Line-Segments

解法1：

依据习惯，我们会定义dp[i][k]表示前i个点如果构造k条线段，总共有多少种方法。

我们考虑我们能如何处理第i个点。我们先考虑如果使用第i个点构造线段，那么以i为右端点的线段长度可以是1,2,...,i。如果这条线段的长度为1，那么dp[i][k]就取决于dp[i-1][k-1]，即前i-1个点构造k-1条线段有多少种方法。同理，如果这条线段的长度为2，那么dp[i][k]就取决于dp[i-2][k-1]... 综上，dp[i][k] = sum {dp[j][k-1]} j=0,1,2...,i-1

但是我们还需要考虑另一种情况：我们不使用第i个点构造线段，那么相当于以i为右端点往左看起，有一段空置的长度，这个长度同样可以是1,2,...,i-1。如果这条空置长度为1，那么dp[i][k]是否就取决于dp[i-1][k]呢？注意，答案是否定的。因为根据dp[i-1][k]的定义，它的计数包括了第i-1个点没有被用来构造线段的情况。如果第i-1个点没有被用来构造线段，那么之前假定的“以i为右端点的、空置长度为1”就不再成立。这样的计数是有问题的。

所以解决方法是什么呢？那就是对于dp[i][k]的计数要分成两种情况来：用dp0[i][k]表示第i个点没有被用来构造线段时、前i个点构造出k条线段的方案数；用dp1[i][k]表示第i个点被用来构造线段时、前i个点构造出k条线段的方案数。同时作为两者的总和，dp[i][k] = dp0[i][k] + dp1[i][k]。

对于dp1[i][k]而言，我们分类的依据就是第i个点被用来构造线段时的长度。根据长度的范围1,2,...i，我们依然有dp1[i][k] = sum {dp[j][k-1]} j=0,1,2...,i-1。注意等式后面的是dp。

对于dp0[i][k]而言，我们分类的依据就是第i个点没有被用来构造线段，那么它之前的空置长度。根据空置长度的范围1,2,...i，分别对应的是第i-1个点、第i-2个点...需要被用来构造线段。所以我们有d0[i][k] = sum {dp1[j][k-1]} j=0,1,2...,i-1。

所以大致的状态转移框架就是：

for (int i=0; i<n; i++)
  for (int k=0; k<=i; k++)
  {
    for (int j=0; j<i; j++)
    {
      dp1[i][k] += dp0[j][k-1] + dp1[j][k-1];
      dp0[i][k] += dp1[j][k];
    }
  }

最终的答案是dp0[n-1][k]+dp1[n-1][k].

上述的时间复杂度是O(N^3)，会超时。如何改进呢？其实内循环所累加的就是dp0[...][k]和dp1[...][k]关于第一个下标的前缀和（从0到i-1）.所以我们可以维护一个前缀和数组sum0[i][k]，表示从dp[0][k]累加到dp[i][k]，类似的也可以定义sum1[i][k]. 于是我们改进一下：

for (int i=0; i<n; i++)
  for (int k=0; k<=i; k++)
  {
    dp1[i][k] = sum0[i-1][k-1] + sum1[i-1][k-1];
    dp0[i][k] = sum1[i-1][k]
  
    sum0[i][k-1] = sum0[i-1][k-1] + dp0[i][k-1];
    sum1[i][k] = sum1[i-1][k] + dp1[i][k];
  }

在每次循环中，处理完dp[i][k]后记得更新一下sum0[i][k-1]和sum1[i][k]。这样的时间复杂度就降为了o(N^2).

对于初始条件，我们需要注意的是dp0[i][0]，前i个点构造0条线段，方法数就是1；相应地，sum0[i][0] = i+1;

解法2：

我们仍然可以定义dp[i][k]表示前i个点如果构造k条线段，总共有多少种方法。

当我们考察第i个点用来构造线段时，dp[i][k]依然可以写作dp[i][k] = sum {dp[j][k-1]} j=0,1,2...,i-1

当我们考察第i个点不用来构造线段时，可以不必想解法1那样想得复杂。事实上，这种情况下就有dp[i][k] = dp[i-1][k].我们不需要根据空置长度来分类。

因此，总的状态转移方程是：dp[i][k] = dp[i-1][k] + sum {dp[j][k-1]} j=0,1,2...,i-1. 我们只需要定义一个前缀和数组 sum[i][k]表示dp[0..i][k]的和。

        for (int i=1; i<n; i++)
            for (int k=1; k<=min(i,K); k++)
            {
                dp[i][k] += dp[i-1][k] + sum[i-1][k-1];            
                sum[i][k] = sum[i-1][k] + dp[i][k];
            }