度度熊最近对全排列特别感兴趣,对于1到n的一个排列, 度度熊发现可以在中间根据大小关系插入合适的大于和小于符号(即 ‘>’ 和 ‘<’ )使其成为一个合法的不等式数列。 但是现在度度熊手中只有k个小于符号即(‘<’‘)和n-k-1个大于符号(即’>’), 度度熊想知道对于1至n任意的排列中有多少个排列可以使用这些符号使其为合法的不等式数列。

输入包括一行,包含两个整数n和k(k < n ≤ 1000)

输出满足条件的排列数,答案对2017取模。

题解：这道题还是应该用DP。不过递推公式不太好找吧，而且是二维DP。 dp[i][j]表示有i个数字和j个 < 号的答案。递推表达式有四种情况： 以i = 2，j = 1为例：

1.将 i+1 插入到当前序列的最左端，即原为 1 < 2 –> 3 > 1 < 2 则相当于增加了一个 > 号

2.将 i+1 插入到当前序列的最右端，即原为 1 < 2 –> 1 < 2 < 3 则增加了一个 < 号

3.将 i+1 插入到一个小于号中，即 1 < 2 –> 1 < 3 > 2 则增加了一个 > 号

4.将 i+1 插入到一个大于号中，即 2 > 1 –> 2 < 3 > 1 则增加了一个 < 号使其为合法的不等式数列。

则dp[i][j]的结果为一下四种情况之和：

1. dp[i-1][j] 将i加到序列的最左端。
2. dp[i-1][j-1] 将i加到序列的最右端。
3. dp[i-1][j]*j 将i加到任意一个小于号之间
4. dp[i-1][j-1]*(i-j-1) 将i加到任意一个大于号之间

则递推公式为 dp[i][j] = dp[i-1][j-1] * (i-j) + dp[i-1][j] * (j+1)