?LeetCode刷題實戰(zhàn)629：K個逆序?qū)?shù)組

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.

給出兩個整數(shù) n 和 k，找出所有包含從 1 到 n 的數(shù)字，且恰好擁有 k 個逆序?qū)Φ牟煌臄?shù)組的個數(shù)。

逆序?qū)Φ亩x如下：對于數(shù)組的第i個和第 j個元素，如果滿i < j且 a[i] > a[j]，則其為一個逆序?qū)Γ环駝t不是。

由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。

示例 1:

輸入: n = 3, k = 0
輸出: 1
解釋: 
只有數(shù)組 [1,2,3] 包含了從1到3的整數(shù)并且正好擁有 0 個逆序?qū)Α?br mpa-from-tpl="t">
示例 2:

輸入: n = 3, k = 1
輸出: 2
解釋: 
數(shù)組 [1,3,2] 和 [2,1,3] 都有 1 個逆序?qū)Α?/p>

主要思路：

（1）動態(tài)規(guī)劃；

（2）dp[ i ][ j ]表示i個數(shù)時，組成 j 個逆序?qū)r，有多少種方法，對于第 i 個數(shù)，可以在原數(shù)組中插入不同的位置，從而增加0,1，……，i-1個逆序?qū)Γ蔰p[ 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];
????}
};