对于permutation类型的DP题有着类似的套路。其核心就是，任意一个长度为n的permutation的前i个元素，可以一一对应于一个长度为i的permutation。所以对于长度为n的permutation做动态规划时，对于状态变量dp[i]（长度为n的permutation的前i个元素组成的、符合条件的序列个数），都可以等效看做是长度为i的（即1-i组成的）、符合条件的permutation个数。
因为本题涉及逆序对的数目，并且题目数据量给出的逆序对数目不超过400，故我们可以将其作为状态变量的一个下标。即我们定义dp[i][j]表示1-i组成的permutation里、逆序对数目是j的排列的个数。
对于前i个元素组成的permutation，能允许有多少逆序对呢？这取决于requirements给出的约束。举个例子，如果requirement要求在第p位有a个逆序对，在第q位有b个逆序对，并且恰好有p<=i<=q（即p和q是i最贴近的两个约束点），那么对于dp[i][j]而言，j的取值就是a<=j<=b.
如何求解dp[i][j]呢？我们需要寻找它与前驱状态dp[i-1][k]的关系。注意到相对于dp[i-1][]，我们在permutation中引入了新元素i，如果将i放在排列的最后，那么它不会引入任何新的逆序对。如果将i放在排列的倒数第二个位置，那么会引入一个逆序对... 依次类推，如果前驱状态dp[i-1][k]已经有k个逆序对，那么相对于j而言，我们需要再引入j-k个逆序对。这能否实现呢？其实只需要满足在i-1的排列中至少有j-k个元素即可，即j-k<=i-1。故
for (int i=1; i<=n; i++)
{
int a = ... , b = ... ;
for (int j=a; j<=b; j++)
for (int k=0; k<=j; k++)
{
if (j-k <= i-1)
dp[i][j] += dp[i-1][k];
}
}注意到，当处理完requirement的最后一个约束位置i后，此后上限b就不存在了。此时意味还有t = n-i个元素没有加入排列。注意这t个元素不能加入前i个元素组成的排列里，否则会违反在i处的约束；但是这t个元素本身可以在排列之后任意混排，不影响之前的requirement。故最终的答案就是dp[i][r]*t!，其中r表示requirement在i处的逆序对数目要求。