|
25 | 25 | */ |
26 | 26 | publicclass_629 { |
27 | 27 |
|
28 | | -/**reference: https://leetcode.com/articles/k-inverse-pairs-array/#approach-5-another-optimized-dynamic-programming-approachaccepted |
29 | | - * and |
30 | | - * https://discuss.leetcode.com/topic/93815/java-dp-o-nk-solution*/ |
31 | | -publicintkInversePairs(intn,intk) { |
32 | | -intmod =1000000007; |
33 | | -if (k >n * (n -1) /2 ||k <0) { |
34 | | -return0; |
35 | | - } |
36 | | -if (k ==0 ||k ==n * (n -1) /2) { |
37 | | -return1; |
38 | | - } |
39 | | -long[][]dp =newlong[n +1][k +1]; |
40 | | -dp[2][0] =1; |
41 | | -dp[2][1] =1; |
42 | | -for (inti =3;i <=n;i++) { |
43 | | -dp[i][0] =1; |
44 | | -for (intj =1;j <=Math.min(k,i * (i -1) /2);j++) { |
45 | | -dp[i][j] =dp[i][j -1] +dp[i -1][j]; |
46 | | -if (j >=i) { |
47 | | -dp[i][j] -=dp[i -1][j -i]; |
| 28 | +publicstaticclassSolution1 { |
| 29 | + |
| 30 | +/** |
| 31 | + * reference: https://leetcode.com/articles/k-inverse-pairs-array/#approach-5-another-optimized-dynamic-programming-approachaccepted |
| 32 | + * and |
| 33 | + * https://discuss.leetcode.com/topic/93815/java-dp-o-nk-solution |
| 34 | + */ |
| 35 | +publicintkInversePairs(intn,intk) { |
| 36 | +intmod =1000000007; |
| 37 | +if (k >n * (n -1) /2 ||k <0) { |
| 38 | +return0; |
| 39 | + } |
| 40 | +if (k ==0 ||k ==n * (n -1) /2) { |
| 41 | +return1; |
| 42 | + } |
| 43 | +long[][]dp =newlong[n +1][k +1]; |
| 44 | +dp[2][0] =1; |
| 45 | +dp[2][1] =1; |
| 46 | +for (inti =3;i <=n;i++) { |
| 47 | +dp[i][0] =1; |
| 48 | +for (intj =1;j <=Math.min(k,i * (i -1) /2);j++) { |
| 49 | +dp[i][j] =dp[i][j -1] +dp[i -1][j]; |
| 50 | +if (j >=i) { |
| 51 | +dp[i][j] -=dp[i -1][j -i]; |
| 52 | + } |
| 53 | +dp[i][j] = (dp[i][j] +mod) %mod; |
48 | 54 | } |
49 | | -dp[i][j] = (dp[i][j] +mod) %mod; |
50 | 55 | } |
| 56 | +return (int)dp[n][k]; |
51 | 57 | } |
52 | | -return (int)dp[n][k]; |
53 | 58 | } |
54 | 59 | } |