|
| 1 | +// Bottom-up DP, Time O(n^2 * k) and Space O(n * k) |
| 2 | +classSolution { |
| 3 | +funkInversePairs(n:Int,k:Int):Int { |
| 4 | +val mod=1_000_000_007 |
| 5 | +val dp=Array (n+1) {LongArray (k+1) } |
| 6 | + |
| 7 | + dp[0][0]=1 |
| 8 | +for (iin1..n) { |
| 9 | +for (jin0..k) { |
| 10 | +for (pin0 until i) { |
| 11 | +if (j- p>=0) |
| 12 | + dp[i][j]= (dp[i][j]+ dp[i-1][j- p])% mod |
| 13 | + } |
| 14 | + } |
| 15 | + } |
| 16 | + |
| 17 | +return dp[n][k].toInt() |
| 18 | + } |
| 19 | +} |
| 20 | + |
| 21 | +// Space optimized Bottom-up DP, Time O(n^2 * k) and Space O(k) |
| 22 | +classSolution { |
| 23 | +funkInversePairs(n:Int,k:Int):Int { |
| 24 | +val mod=1_000_000_007 |
| 25 | +var dp=LongArray (k+1) |
| 26 | + |
| 27 | + dp[0]=1 |
| 28 | +for (iin1..n) { |
| 29 | +val newDp=LongArray (k+1) |
| 30 | +for (jin0..k) { |
| 31 | +for (pin0 until i) { |
| 32 | +if (j- p>=0) |
| 33 | + newDp[j]= (newDp[j]+ dp[j- p])% mod |
| 34 | + } |
| 35 | + } |
| 36 | + dp= newDp |
| 37 | + } |
| 38 | + |
| 39 | +return dp[k].toInt() |
| 40 | + } |
| 41 | +} |
| 42 | + |
| 43 | +// Space optimized DP + Sliding window Time O(n * k) and Space O(k) |
| 44 | +classSolution { |
| 45 | +funkInversePairs(n:Int,k:Int):Int { |
| 46 | +val mod=1_000_000_007 |
| 47 | +var prev=LongArray (k+1) |
| 48 | + |
| 49 | + prev[0]=1 |
| 50 | +for (iin1..n) { |
| 51 | +val cur=LongArray (k+1) |
| 52 | +var total=0L |
| 53 | +for (jin0..k) { |
| 54 | +if (j>= i) |
| 55 | + total-= prev[j- i] |
| 56 | + total= (total+ prev[j]+ mod)% mod |
| 57 | + cur[j]= total |
| 58 | + } |
| 59 | + prev= cur |
| 60 | + } |
| 61 | + |
| 62 | +return prev[k].toInt() |
| 63 | + } |
| 64 | +} |