add 629

fishercoder1534 · fishercoder1534 · commit 2ab632f4dbad · 2017-07-29T08:35:07.000-07:00
diff --git a/README.md b/README.md
@@ -38,6 +38,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |632|[Smallest Range](https://leetcode.com/problems/smallest-range/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_632.java) | O(n*logk) |O(k) | Hard| Heap
 |631|[Design Excel Sum Formula](https://leetcode.com/problems/design-excel-sum-formula/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_631.java) | | | Hard| Design, Topological Sort
 |630|[Course Schedule III](https://leetcode.com/problems/course-schedule-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_630.java) | O(n*logn) |O(n) | Hard| Heap, Greedy
+|629|[K Inverse Pairs Array](https://leetcode.com/problems/k-inverse-pairs-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_629.java) | O(n*k) |O(n*k) | Hard| DP
 |628|[Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_628.java) | O(nlogn) |O(1) | Easy |
 |625|[Minimum Factorization](https://leetcode.com/problems/minimum-factorization/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_625.java) | O(?) |O(?) | Medium | 
 |624|[Maximum Distance in Arrays](https://leetcode.com/problems/maximum-distance-in-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_624.java) | O(nlogn) |O(1) | Easy | Sort, Array
diff --git a/src/main/java/com/fishercoder/solutions/_629.java b/src/main/java/com/fishercoder/solutions/_629.java
@@ -25,7 +25,24 @@
  */
 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) {
-        return 0;
+        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];
     }
 }
