个人免费网站创建入口,高端的网站建设,成都建站模板网站开发,销售平台网站建设629. K个逆序对数组
给出两个整数 n 和 k#xff0c;找出所有包含从 1 到 n 的数字#xff0c;且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下#xff1a;对于数组的第i个和第 j个元素#xff0c;如果满i j且 a[i] a[j]#xff0c;则其为一个逆…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 个逆序对。示例 2:输入: n 3, k 1
输出: 2
解释:
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。说明:
n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。
解题思路
状态转移公式的推导
例如当n3 k2时xxx代表n3时的逆序对数组的任意情况我们需要计算n4并且k2的情况可以看成是向n3时的所有逆序对数组插入值4下面是插入的几种情况
4xxx因为4是当前的最大值必然大于后面3个元素所以能产生3对逆序对超出了k2x4xx因为4是当前的最大值必然大于后面2个元素所以必然能产生2对逆序对又因为我们需要逆序对的数量k2所以只能从n2k0的情况转移而来xx4x因为4是当前的最大值必然大于后面1个元素所以必然能产生1对逆序对又因为我们需要逆序对的数量k2所以只能从n2k1的情况转移而来xxx4因为4在最末尾所以不能产生新的逆序对又因为我们需要逆序对的数量k2所以只能从n2k2的情况转移而来
因此我们可以得出 dp[n1][k]dp[n][k-1]dp[n][k-2]…dp[n][k-n1]
使kk1得 dp[n1][k1]dp[n][k]dp[n][k-1]…dp[n][k-n2]
两式相减得dp[n][k]dp[n-1][k]dp[n][k-1]-dp[n-1][k-n]
代码
class Solution {
public:int kInversePairs(int n, int k) {vectorvectorint dp(n1,vectorint(k1,0));dp[1][0]1;int mod1000000007;for (int i 2; i n; i) {for (int j 0; j k; j) {dp[i][j]dp[i-1][j](j-10?dp[i][j-1]:0)-(j-i0?dp[i-1][j-i]:0);if (dp[i][j]mod)dp[i][j]-mod;else if (dp[i][j]0)dp[i][j]mod;}}return dp[n][k];}
};
