K 个逆序对数组

/*
  思路：
  使用动态规划和Java Stream API来计算 dp 数组。与传统动态规划类似，利用前缀和来优化内部循环。
  通过计算前缀和来减少时间复杂度。dp[i][j] = prefix[j] - prefix[j - i]。
  初始化：dp[0][0] = 1，其他 dp[0][j] = 0（j > 0）。
  我们要求的结果是 dp[n][k]，结果需要对 10^9 + 7 取模。
*/
import java.util.stream.IntStream;
 
public class KInversePairsStream {
    public int kInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int[] prefix = new int[k + 1];
            prefix[0] = dp[i - 1][0];
            IntStream.range(1, k + 1).forEach(j -> prefix[j] = (prefix[j - 1] + dp[i - 1][j]) % MOD);
            IntStream.range(0, k + 1).forEach(j -> {
                dp[i][j] = prefix[j];
                if (j >= i) {
                    dp[i][j] = (dp[i][j] - prefix[j - i] + MOD) % MOD;
                }
            });
        }
        return dp[n][k];
    }
}