For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.
For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].
Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.
给出两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下:对于数组的第i个和第 j个元素,如果满i < j且 a[i] > a[j],则其为一个逆序对;否则不是。
由于答案可能很大,只需要返回 答案 mod 109 + 7 的值。
示例 1:输入: n = 3, k = 0输出: 1解释: 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。示例 2:输入: n = 3, k = 1输出: 2解释: 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。
主要思路:
(1)动态规划;
(2)dp[ i ][ j ]表示i个数时,组成 j 个逆序对时,有多少种方法,对于第 i 个数,可以在原数组中插入不同的位置,从而增加0,1,……,i-1个逆序对,故dp[ i ][ j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+……+dp[i -1][ j-(i-1)];
(3)又有dp[ i ][ j - 1]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+……+dp[i -1][ j-i];,则两个式子相减有 dp[ i ][ j ]-dp[ i ][ j-1 ]=dp[i-1][ j ]-dp[ i-1 ][ j-i]; 既dp[ i ][ j ]=dp[ i ][ j-1 ]+dp[i-1][ j ]-dp[ i-1 ][ j-i];
class Solution {public: int kInversePairs(int n, int k) { vector<vector<long>> dp(n+1,vector<long>(k+1,0)); for(int i=1;i<=n;++i){//初始化,没有逆序的情形 dp[i][0]=1; } for(int i=2;i<=n;++i){ for(int j=1;j<=k;++j){ if(j>=i){//对于 j>=i dp[i][j]=dp[i][j-1]+(dp[i-1][j]+1000000007-dp[i-1][j-i]); } else{ dp[i][j]=dp[i][j-1]+dp[i-1][j];//少了上述的一项 } dp[i][j]%=1000000007; } } return dp[n][k]; }};
`单行代码`