给定n,k,如何求出1~n排列中所有逆序数为k者?
如题
[解决办法]
比如说5个数,逆序数为7
12345 每个位置上对应的最大逆序为 43210,
让第1位为0的话,后面最大逆序为6,因此无解
让第1位为1的话,后面最大逆序为6,有1个解
让第1位为2的话,问题转化为后4个为5
让第1位为3的话,问题转化为后4个为4
让第1位为4的话,问题转化为后4个为3
反正就是这样递归下去,中间用个hash存储算过的,如果已经算过,直接从hash里面读取,其实就相当于DP[i,j]
不过算的比较有目的性,效率可能同动态规划差不多,也许还快一点点吧!