【leetcode dp】629. K Inverse Pairs Array

2023-09-09 阅读 30 评论 0

摘要：https://leetcode.com/problems/k-inverse-pairs-array/description/ 【题意】 leetcode1120？给定n和k，求正好有k个逆序对的长度为n的序列有多少个，0<=k<=1000, 1<=n<=1000，答案模1e9+7 【思路】 dp[i][j]表示正好有j个

https://leetcode.com/problems/k-inverse-pairs-array/description/

【题意】

leetcode1120？给定n和k，求正好有k个逆序对的长度为n的序列有多少个，0<=k<=1000, 1<=n<=1000，答案模1e9+7

【思路】

dp[i][j]表示正好有j个逆序对的长度为i的序列的方案数，最终我们要求的就是dp[n][k]

leetcode124，考虑dp[i+1][j]和dp[i][j]的关系，长度为i+1的序列相当于在长度为i的序列中插入一个数，那么有

xxxx#

xxx#x

LeetCode Online Judge、xx#xx

x#xxx

#xxxx

则dp[i+1][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+...+dp[i-1][j-(i-1)]

这样写的转移复杂度比较大，会T

可以优化一下，考虑dp[i][j+1]和dp[i][j]的关系，可以得到dp[i][j]=dp[i][j-1]+dp[i][j-1]-dp[i-1][j-i]

【Accepted】

 1 class Solution {
 2 public:
 3     int kInversePairs(int n, int k) {
 4         if(k==0) return 1;
 5         const int maxn=1e3+2;
 6         const int mod=1e9+7;
 7         int dp[maxn][maxn];
 8         memset(dp,0,sizeof(dp));
 9         for(int i=1;i<maxn;i++) dp[i][0]=1;
10         for(int i=1;i<=n;i++){
11             for(int j=1;j<=min(k,i*(i-1)/2);j++){
12                 dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
13                 dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
14                 if(j>=i)
15                     dp[i][j]=(dp[i][j]-dp[i-1][j-i]+mod)%mod;
16             }
17         }
18         return dp[n][k]%mod;
19     }
20 };