@dreamchase said in Java DP O(nk) solution:

dp[n][k] = dp[n][k-1]+dp[n-1][k]-dp[n-1][k-n] since this is your formula.

Why dp[i][j] can equals to "dp[i][j-1] + dp[i-1][j]; "

Should we prove that

when k<n

dp[n][k] = dp[n][k-1]+dp[n-1][k] ?

K Inverse Pairs Array