Помогите решить проблему с ДП.

Я не уверен, что понимаю вашу идею решения, но я описываю свое решение AC:

Я использую функцию с запоминанием, но вы можете переписать ее с помощью нерекурсивного DP.

Допустим, у нас есть наши интервалы в массиве

пара а[100]; где a[i].first — начало интервала, а a[i].second — конец интервала.

Сначала отсортируйте этот массив по begin (поведение алгоритма сортировки stl по умолчанию с компаратором пар по умолчанию).

Теперь представьте, что мы «ставим» интервалы один за другим от начала до конца.

пусть f(int x, int prev) возвращает количество способов закончить заполнение, если в настоящее время последний интервал равен x, а предыдущий равен «prev».

мы рассчитаем его следующим образом:

int f(int x, int prev) {
  // if already calculated dp[x][prev], return it. Otherwise, calculate it
  if (dp[x][prev] != -1) {
    return dp[x][prev];
  }
  if (a[x].second == m) {
    return dp[x][prev] = 1; // it means - X is last interval in day
  }
  else {
    dp[x][prev] = 0;
    for (int i = x + 1; i < n; ++i) { // try to select next interval
      if (a[i].first <= a[x].second && // there must be not empty space after x interval
          a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless
          a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless
          a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless.  
        dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000;
      }
    }
  }
  return dp[x][prev];
}

После этого нам нужно вызвать эту функцию для каждой пары интервалов, первый из которых начинается с 0, а второй связан с первым:

for (int i = 0; i < n; ++i) {
  if (a[i].first == 0) {
     for (int j = i + 1; j < n; ++j) {
        if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless
            a[j].first <= a[i].second && // there must be no space after i interval
            a[j].second > a[i].second) { // in opposite case j will be useless
           res = (res + f(j, i)) % 100000000;
        }
     }
     // also we need to check the case when we use only one interval:
     if (a[i].second == m) {
        res = (res + 1) % 100000000;
     }
  }
}

После этого нам нужно только распечатать res.