给定一个数组，一个反转被定义为一对a[i]，a[j]，这样a[i]>a[j]和i
null
例如：
Input : N = 3, K = 1Output : 2Explanation : Total Permutation of first N number,123, 132, 213, 231, 312, 321Permutation with 1 inversion : 132 and 213Input : N = 4, K = 2Output : 5
解决这个问题的一个天真的方法是记下来 全部的 置换然后检查其中的反转计数，但迭代置换本身需要O（N！）时间太长了。
我们可以使用动态规划方法来解决这个问题。下面是递归公式。
If N is 0, Count(0, K) = 0If K is 0, Count(N, 0) = 1 (Only sorted array)In general case, If we have N number and require K inversion, Count(N, K) = Count(N - 1, K) + Count(N – 1, K - 1) + Count(N – 1, K – 2) + .... + Count(N – 1, 0)
这部电影怎么样 上面的递归公式有效吗？ 如果我们有N个数，并且想要有K个置换，并且假设（N–1）数的所有置换都写在某个地方，那么新的数（N个数和最大的数）需要放在（N–1）数的所有置换中，并且那些在加上这个数后倒数变为K的数应该加到我们的答案中。现在让（K–3）倒数的（N–1）个数的排列集合，现在我们可以把这个新的最大数放在从最后一个数开始的第3位，那么倒数计数将是K，所以计数（N–1，K–3）应该加到我们的答案中，同样的参数也可以用于另一个倒数，我们将达到上面的递归作为最终答案。
下面的代码是按照上述递归以记忆的方式编写的。
C++
// C++ program to find number of permutation // with K inversion using Memoization #include <bits/stdc++.h> using namespace std; // Limit on N and K const int M = 100; // 2D array memo for stopping // solving same problem again int memo[M][M]; // method recursively calculates // permutation with K inversion int numberOfPermWithKInversion( int N, int K) { // base cases if (N == 0) return 0; if (K == 0) return 1; // if already solved then // return result directly if (memo[N][K] != 0) return memo[N][K]; // calling recursively all subproblem // of permutation size N - 1 int sum = 0; for ( int i = 0; i <= K; i++) { // Call recursively only // if total inversion // to be made are less // than size if (i <= N - 1) sum += numberOfPermWithKInversion(N - 1, K - i); } // store result into memo memo[N][K] = sum; return sum; } // Driver code int main() { int N = 4; int K = 2; cout << numberOfPermWithKInversion(N, K); return 0; } |
JAVA
// Java program to find number of permutation with // K inversion using Memoization import java.io.*; class GFG { // Limit on N and K static int M = 100 ; // 2D array memo for stopping solving same problem // again static int memo[][] = new int [M][M]; // method recursively calculates permutation with // K inversion static int numberOfPermWithKInversion( int N, int K) { // base cases if (N == 0 ) return 0 ; if (K == 0 ) return 1 ; // if already solved then return result directly if (memo[N][K] != 0 ) return memo[N][K]; // calling recursively all subproblem of // permutation size N - 1 int sum = 0 ; for ( int i = 0 ; i <= K; i++) { // Call recursively only if total inversion // to be made are less than size if (i <= N - 1 ) sum += numberOfPermWithKInversion(N - 1 , K - i); } // store result into memo memo[N][K] = sum; return sum; } // Driver code to test above methods public static void main(String[] args) { int N = 4 ; int K = 2 ; System.out.println(numberOfPermWithKInversion(N, K)); } } // This code is contributed by vt_m. |
Python3
# Python3 program to find number of permutation # with K inversion using Memoization # Limit on N and K M = 100 # 2D array memo for stopping # solving same problem again memo = [[ 0 for i in range (M)] for j in range (M)] # method recursively calculates # permutation with K inversion def numberOfPermWithKInversion(N, K): # Base cases if (N = = 0 ): return 0 if (K = = 0 ): return 1 # If already solved then # return result directly if (memo[N][K] ! = 0 ): return memo[N][K] # Calling recursively all subproblem # of permutation size N - 1 sum = 0 for i in range (K + 1 ): # Call recursively only if # total inversion to be made # are less than size if (i < = N - 1 ): sum + = numberOfPermWithKInversion(N - 1 , K - i) # store result into memo memo[N][K] = sum return sum # Driver code N = 4 ; K = 2 print (numberOfPermWithKInversion(N, K)) # This code is contributed by Anant Agarwal. |
C#
// C# program to find number of // permutation with K inversion // using Memoization using System; class GFG { // Limit on N and K static int M = 100; // 2D array memo for stopping // solving same problem again static int [,]memo = new int [M, M]; // method recursively calculates // permutation with K inversion static int numberOfPermWithKInversion( int N, int K) { // base cases if (N == 0) return 0; if (K == 0) return 1; // if already solved then // return result directly if (memo[N, K] != 0) return memo[N, K]; // calling recursively all // subproblem of permutation // size N - 1 int sum = 0; for ( int i = 0; i <= K; i++) { // Call recursively only if // total inversion to be // made are less than size if (i <= N - 1) sum += numberOfPermWithKInversion(N - 1, K - i); } // store result into memo memo[N, K] = sum; return sum; } // Driver Code static public void Main () { int N = 4; int K = 2; Console.WriteLine(numberOfPermWithKInversion(N, K)); } } // This code is contributed by ajit |
PHP
<?php // PHP program to find number of permutation // with K inversion using Memoization // method recursively calculates // permutation with K inversion function numberOfPermWithKInversion( $N , $K ) { $memo = array (); // base cases if ( $N == 0) return 0; if ( $K == 0) return 1; // if already solved then // return result directly if ( $memo [ $N ][ $K ] != 0) return $memo [ $N ][ $K ]; // calling recursively all subproblem // of permutation size N - 1 $sum = 0; for ( $i = 0; $i <= $K ; $i ++) { // Call recursively only // if total inversion // to be made are less // than size if ( $i <= $N - 1) $sum += numberOfPermWithKInversion( $N - 1, $K - $i ); } // store result into memo $memo [ $N ][ $K ] = $sum ; return $sum ; } // Driver code $N = 4; $K = 2; echo numberOfPermWithKInversion( $N , $K ); // This code is contributed // by Akanksha Rai(Abby_akku) ?> |
Javascript
<script> // Javascript program to find number of // permutation with K inversion using // Memoization // Limit on N and K let M = 100; // 2D array memo for stopping solving // same problem again let memo = new Array(M); for (let i = 0; i < M; i++) { memo[i] = new Array(M); for (let j = 0; j < M; j++) { memo[i][j] = 0; } } // Method recursively calculates permutation // with K inversion function numberOfPermWithKInversion(N, K) { // base cases if (N == 0) return 0; if (K == 0) return 1; // If already solved then return // result directly if (memo[N][K] != 0) return memo[N][K]; // Calling recursively all subproblem of // permutation size N - 1 let sum = 0; for (let i = 0; i <= K; i++) { // Call recursively only if total inversion // to be made are less than size if (i <= N - 1) sum += numberOfPermWithKInversion( N - 1, K - i); } // Store result into memo memo[N][K] = sum; return sum; } // Driver code let N = 4; let K = 2; document.write(numberOfPermWithKInversion(N, K)); // This code is contributed by divyesh072019 </script> |
输出
5
时间复杂性： O（N*N*K）
优化方法： 使用表格和累积和
C++
// C++ program to find number of permutation // with K inversions #include <bits/stdc++.h> using namespace std; int numberOfPermWithKInversions( int N, int K) { vector<vector< int >> dp(N+1,vector< int >(K+1)); // As for k=0, number of permutations is 1 for every N for ( int i = 1; i <= N; i++) dp[i][0] = 1; // Using Dynamic Programming with cumulative sum for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= K; j++) { // This is same as val = dp[i-1][j] - dp[i-1][j-i] // i.e. dp[i-1][j........j-i], just taking care of // boundaries int val = dp[i-1][j]; if (j >= i) val -= dp[i-1][j-i]; dp[i][j] = dp[i][j-1] + val; } } // And, in the end calculate the dp[n][k] // which is dp[n][k]-dp[n][k-1] int ans = dp[N][K]; if (K >= 1) ans -= dp[N][K-1]; return ans; } int main() { int N = 4; int K = 2; cout << numberOfPermWithKInversions(N,K) << "" ; return 0; } |
输出
5
时间复杂性： O（N*K）
本文由 乌特卡什·特里维迪 和 安基特·库马尔·夏尔马 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
