把一个排列p变成1,2,...,n可以反过来看成1,2,...,n到p 把p分解乘循环 如果一个循环有n个元素 需要n-1次交换 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (i-1); 代表i个元素 交换j次变成1,2,...,n,的种数 对于元素i 他可以自己成为一个循环那么交换次数不变 种数+1 就是 dp[i-1][j]

题目链接：uva 11077 - Find the Permutations 题目大意：给定一个1~n的排序，可以通过一系列的交换变成1，2，…,n, 给定n和k，统计有多少个排列至少需要交换k次才能变成有序的序列。 解题思路：给定一个序列P，可以将该序列看做是一个置换，从有序序列，开始，需要多少次回到有序序列。将P的循环分解，循环长度为1的需要0次，长度为2的需要1次，循环长度为n的需

（一）前言         线性动态规划只需考虑一个变量，而二维动规需要两个变量来实现动态规划方程。定义两个变量需要根据具体问题具体分析。常见的二维动规问题类型个人划分为以下几种类型：（1）字符串DP（2）N区间M问题（3）矩阵类DP问题（4）区间动态规划（单独介绍）（5）背包问题（单独介绍）。其中4和5虽然也采用二维形式，但问题比较典型，一般被划分为专有类别，因此本文不做具体阐述。 （二）