脚本宝典收集整理的这篇文章主要介绍了629. K个逆序对数组 力扣（困难） 区间动态规划，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。
示例 1:
输入: n = 3, k = 0输出: 1解释: 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
题解：
代码改进：从TLE到AC
代码：
TLE：
class Solution { public: long long dp[1005][1005]; int kInversePairs(int n, int k) { // dp[i][j]：表示i个数字1~i，逆序对数为j的方案数。 long long mo=1e9+7; dp[0][0]=1; for(int i=1;i<=n;i++) // 开始放置数字i for(int j=0;j<=k;j++) // 逆序对个数 { for(int pos=1;pos<=i;pos++) if(j>=i-pos) dp[i][j]=(dp[i][j]+dp[i-1][j-(i-pos)])%mo; } return dp[n][k]; } };
以上是脚本宝典为你收集整理的629. K个逆序对数组 力扣（困难） 区间动态规划全部内容，希望文章能够帮你解决629. K个逆序对数组 力扣（困难） 区间动态规划所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。