package com.fishercoder.solutions;

/**
 * 629. K Inverse Pairs Array
 *
 * Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.
 We define an inverse pair as following: For ith and jth element in the array,
 if i < j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.
 Since the answer may very large, the answer should be modulo 109 + 7.

 Example 1:
 Input: n = 3, k = 0
 Output: 1
 Explanation:
 Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

 Example 2:
 Input: n = 3, k = 1
 Output: 2
 Explanation:
 The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

 Note:
 The integer n is in the range [1, 1000] and k is in the range [0, 1000].
 */
public class _629 {

    /**reference: https://leetcode.com/articles/k-inverse-pairs-array/#approach-5-another-optimized-dynamic-programming-approachaccepted
     * and
     * https://discuss.leetcode.com/topic/93815/java-dp-o-nk-solution*/
    public int kInversePairs(int n, int k) {
        int mod = 1000000007;
        if (k > n * (n - 1) / 2 || k < 0) {
            return 0;
        }
        if (k == 0 || k == n * (n - 1) / 2) {
            return 1;
        }
        long[][] dp = new long[n + 1][k + 1];
        dp[2][0] = 1;
        dp[2][1] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= Math.min(k, i * (i - 1) / 2); j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                if (j >= i) {
                    dp[i][j] -= dp[i - 1][j - i];
                }
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }
        return (int) dp[n][k];
    }
}

@@ -807,19 +807,72 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A%0A        /**%0A         * 
 referenc
@@ -1002,14 +1002,22 @@
     
+    
 * and%0A
+    
     
@@ -1081,19 +1081,33 @@
 solution
-*/%0A
+%0A         */%0A    
     publ
@@ -1151,16 +1151,20 @@
         
+    
 int mod 
@@ -1177,16 +1177,20 @@
 000007;%0A
+    
         
@@ -1233,24 +1233,28 @@
             
+  
+  
 return 0;%0A  
@@ -1251,34 +1251,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         if (k ==
@@ -1323,24 +1323,28 @@
             
+ 
+   
 return 1;%0A  
@@ -1349,26 +1349,33 @@
         
-%7D%0A
+    %7D%0A   
         
 long%5B%5D%5B%5D
@@ -1366,16 +1366,17 @@
         
+ 
 long%5B%5D%5B%5D
@@ -1409,24 +1409,28 @@
 1%5D;%0A        
+    
 dp%5B2%5D%5B0%5D = 1
@@ -1435,24 +1435,28 @@
  1;%0A        
+ 
+   
 dp%5B2%5D%5B1%5D = 1
@@ -1457,32 +1457,36 @@
 1%5D = 1;%0A        
+  
+  
 for (int i = 3; 
@@ -1508,24 +1508,28 @@
             
+    
 dp%5Bi%5D%5B0%5D = 1
@@ -1522,32 +1522,36 @@
   dp%5Bi%5D%5B0%5D = 1;%0A
+    
             for 
@@ -1612,32 +1612,36 @@
                 
+    
 dp%5Bi%5D%5Bj%5D = dp%5Bi%5D
@@ -1676,24 +1676,28 @@
             
+    
 if (j %3E= i) 
@@ -1710,32 +1710,36 @@
                 
+   
+ 
 dp%5Bi%5D%5Bj%5D -= dp%5Bi
@@ -1752,16 +1752,20 @@
 j - i%5D;%0A
+    
         
@@ -1782,32 +1782,36 @@
                 
+    
 dp%5Bi%5D%5Bj%5D = (dp%5Bi
@@ -1841,26 +1841,33 @@
         
+ 
-%7D%0A
+   %7D%0A   
         
 %7D%0A      
@@ -1850,34 +1850,39 @@
    %7D%0A           
+ 
 %7D%0A
+    
         return (
@@ -1896,16 +1896,26 @@
 %5Bn%5D%5Bk%5D;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 629