629. K Inverse Pairs Array 自制答案 - 涂修竹的专栏 - 博客频道 - CSDN.NET

629. K Inverse Pairs Array 自制答案 - 涂修竹的专栏 - 博客频道 - CSDN.NET

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For ith and jth element in the array, if i< j and a[i] > a[j] then it's an inverse pair; Otherwise, it's not.

Since the answer may very large, the answer should be modulo 109 + 7.

Example 1:

Input: n = 3, k = 0 Output: 1 Explanation:  Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair. 

Example 2:

Input: n = 3, k = 1 Output: 2 Explanation:  The array [1,3,2] and [2,1,3] have exactly 1 inverse pair. 

Note:

1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

最近专攻动态规划的练习，感觉这道题是一个很好的样本，从中学习到了很多，所以准备整理一下。

参考资料：https://leetcode.com/articles/k-inverse-pairs-array/#approach-5-dynamic-programming-with-cumulative-sumaccepted

1.动态规划

首先，Inverse Pairs Array这个单词翻译到中文大概是"逆对数组"，虽然听起来有点别扭但我们就按照这个翻译好了。

在定义中，数组a中存在第i个和第j个元素，且i<j但a[i]>a[j]，则是一个逆序对。而K Inverse Pairs Array 则是存在k个逆序对的数组。

在这道题的计算中，需要计算前n个数字组成存在k个逆序对的数组的不同排列数量，而这与动态规划息息相关。

当我们添加第n个数字的时候，其目的是为了满足k个逆序对，那么就将有如下几种可能性：

当n处于最后一位，即本身的位置时，没有增加新的逆序对，那么就应该找到前(n-1)个数字时，出现k个逆序对的情况。

当n处于倒数第二位时，增加了一个逆序对，那么就应该找到前(n-1)个数字时，出现(k-1)个逆序对的情况。

…………………………

同理，当n处于第一位的时候，增加了(n-1)个逆序对，那么就应该找到前(n-1)个数字时，出现(k-（n-1）)个逆序对的情况。

在这里我们通常使用一个二维数组dp[n][k]来表示具体情况。表示前n个数字组成存在k个逆序对数组的排列数量，有点像最开始学习背包问题的表达。

那么我们将得到如下公式：

 dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]

 dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]

上下两个公式同时相减，可以得到下式:

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

上面的公式，基本上就是程序中编写的主要部分，但一定要注意的是，k-(n-1)可能会小于0，需要进行处理，当小于0时，dp[n-1][k+1-n]赋值为0即可。

Read full article from 629. K Inverse Pairs Array 自制答案 - 涂修竹的专栏 - 博客频道 - CSDN.NET