[LeetCode] 629. K Inverse Pairs Array

https://leetcode.com/problems/k-inverse-pairs-array/description/?envType=daily-question&envId=2024-01-27

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - K Inverse Pairs Array

문제 유형 : 순열, 조합, 수학, 마호니언 삼각형, 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7.

 

정수 배열 nums가 있다. nums에서의 두 인덱스 i,j에 대해 i가 j의 앞에 있고, 값이 더 큰 경우, 역전된 쌍이라고 한다.

두 정수 n과 k가 주어진다.

1부터 n까지 각 1개씩 구성된 배열들 중, 정확히 k개의 역전쌍이 있는 서로 다른 배열의 개수를 구하시오.

 

 

풀이

dp[i][j] = n=i, k=j인 상황에서의 조건을 만족하는 서로 다른 배열의 개수라고 하자.

 

이 문제는 마호니언 삼각형 문제이다.

dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]라는 점화식을 구할 수 있다.

메모이제이션과 타뷸레이션 중 원하는 방식으로 전개하면 된다.

 

 

코드

C++

 

탑 다운(메모이제이션)

class Solution {
public:
    int dp[1001][1001];
    int MOD = 1e9+7;
    int solve(int n, int k) {
        if(k == 0) return 1;
        if(k < 0 || n <= 0) return 0;
        if(dp[n][k] != -1) return dp[n][k];

        return dp[n][k] = ((solve(n-1, k) + solve(n, k-1))%MOD - solve(n-1, k-n) + MOD) % MOD;
    }

    int kInversePairs(int n, int k) {
        memset(dp, -1, sizeof(dp));
        int ans = solve(n, k);
        return ans;
    }
};

 

바텀 업(타뷸레이션)

class Solution {
public:
    int kInversePairs(int n, int k) {
        int dp[1001][1001];
        const int MOD = 1e9+7;
        dp[0][0] = 1;

        for(int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            long long x = 0;
            for(int j = 1; j <= k; j++) {
                x = dp[i][j-1] + dp[i-1][j];

                if(j >= i) {
                    x += (MOD-dp[i-1][j-i]);
                }
                dp[i][j] = x%MOD;
            }
        }
        return dp[n][k];
    }
};