算法思路

首先，n个不同的数组成排列，要求相邻两者满足特定大小关系.排列的方式是和具体这n个数是多少无关的:只要是n个不同的数，我们都可以把他们组成的排列映射到1到n组成的排列.
考虑满足前n+1个DI关系的排列和满足前n个DI关系的排列之间的关系(满足前n+1个DI关系的排列中共有n+2个数):1到n+2组成的满足前n+1个DI关系的排列，去掉最末尾一个数，剩下的数按大小重新映射到1到n+1，所组成的一定是满足前n个DI关系的前n+1个数的排列.
所以对于n+1个数的满足n个DI关系的排列，我们在末尾”插入”一个满足第n+1个DI关系的数，对这n+2个数重新标号，就能获得一个满足满足n+1个DI关系的排列．
所谓”插入”,重新标号，是指，比如有这样一个排列”1, 2, 3, 4”,我们在末尾插入一个数，大小在2和3之间”1, 2, 3, 4, 2.5”,然后重新标号”1, 2, 4, 5, 3”就得到了一个5个数的排列，而前4个数之间的相对大小关系不变.
注意到排列中最后一个数是多少，会影响可以插入的数的个数.
动态规划的状态：dp[i][j]表示用1..i+1做全排列，满足前i个DI关系，且排列的末尾是j的排列数．
如果第i+1个DI是D:
dp[i + 1][j] = for k = j to i + 2, sum(dp[i][k])
否则:
dp[i + 1][j] = for k = 1 to j, sum(dp[i][k])
状态共N^2个，每个状态转移代价O(N)，但是状态转移可以优化成N状态转移的合计代价为N．总时间复杂度O(N^2)

代码

#include <string>
#include <vector>
#include <numeric>
#include <iostream>
#include <cassert>

using namespace std;

class Solution {
  static const int MOD = 1000000007;
public:
  int numPermsDISequence(string str) {
    int s = str.size();
    std::vector<int> dp(s + 1), dp1(s + 1);
    dp1[0] = 1;
    for (int i = s - 1; i >= 0; --i) {
      if (str[i] == 'D') {
        dp[0] = 0;
        int sum = dp1[0];
        for (int j = 1; j <= s - i; ++j) {
          dp[j] = sum;
          sum += dp1[j];
          sum %= MOD;
        }
      } else {
        dp[s - i] = 0;
        int sum = dp1[s - i];
        for (int j = s - i - 1; j >= 0; --j) {
          sum += dp1[j];
          sum %= MOD;
          dp[j] = sum;
        }
      }
      swap(dp, dp1);
    }
    int ret = 0;
    for (auto v : dp1) {
      ret += v;
      ret %= MOD;
    }
    return ret;
  }
};