題目

解題概念

  • 此題簡單來說，就是我們要在 $1$ 到 $n$ 之間，任意排列數字，使其剛好存在 $k$ 個 Inevrse Pairs
  • 而這題為典型的 Dynamic Programming (DP; 動態規劃)題型，所以要照以下步驟去思考

建立表格

  • 因為我們要求的是kInversePairs(n, k)的解，故可以將運算的值存入以下 block 陣列中，以減輕後續遞迴之運算量

思考遞迴規則

  1. 以kInversePairs(4, 3)如例，等同於求 block[4][3]，則可以視為將 4 插入三個數字間的空隙中

    XXX 代表 [1, 2, 3] 這三個數字的排序組合

  2. 即可推論出 4 種情況

  3. 因此，可推論出 $block[4][3]=block[3][3]+block[3][2]+block[3][1]+block[3][0]$

    • 同理 : $block[4][4] = block[3][4]+block[3][3]+block[3][2]+block[3][1]$

推論出遞迴式

  • 透過以上步驟，可推論出此題之遞迴式 : $$block[n+1][k] = block[n][k] + block[n][k-1]+\cdots+block[n][k-n]$$

  • 若將用 $n$ 取代 $n+1$ 可得 : $$block[n][k] = block[n-1][k] + block[n-1][k-1]+\cdots+block[n-1][k-n+1]$$

  • 進一步化簡 :

    • 第 1 式 :
      $$block[n][k] = block[n-1][k] + block[n-1][k-1]+\cdots+block[n-1][k-n+1] \implies (1)$$
    • 第 2 式 : 用 $k+1$ 取代 $k$
      $$block[n][k+1] = block[n-1][k+1] + block[n-1][k]+\cdots+block[n-1][k-n+2] \implies (2)$$
    • 第 2 式減去第 1 式可得 :
      $$block[n][k+1] = block[n][k] + block[n - 1][k+1] - block[n - 1][k - n + 1]$$
    • 再用 $k$ 取代 $k+1$ :
      $$block[n][k] = block[n][k-1] + block[n - 1][k] - block[n - 1][k - n]$$

  • 其他狀況 :

    • 若 $n = 0$ 時，$block[n][k] = 0$ (因為無數字)
    • 若 $k = 0$ 時，$block[n][k] = 1$ (因為 $k=0$ ，只有一種由小到大之數字排列組合)
    • 當 $k < n$ 時，$block[n - 1][k - n]$ 會出現負數索引值，故結果就會變成$$block[n][k] = block[n][k-1] + block[n - 1][k] - 0$$

  • 因此，最終遞迴式為 :

實際寫Code

  • 目標函式 : kInversePairs(n, k)
    • Input : n: int、k: int
    • Output : int
  • 前置作業 : 
    1
    2
    3
    4
    # 製作一個 (n+1) * (k+1) 之陣列，內容都是 0
    # row : 0 ~ n、column : 0 ~ k
    block = [[0 for x in range(k + 1)] for y in range(n + 1)]
    M = 1000000007
  • 主要程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 經過表格內所有的元素
    for i in range(1, n+1):
        for j in range(0, k+1):

            # 當 j = 0 的情況
            if j == 0 :
                block[i][j] = 1
            else:
                temp = 0

                # 需確認 j 與 i 的大小關係，進而去改變 temp 的算法
                if j - i >= 0 :
                    temp = block[i-1][j-i]
                val = (block[i-1][j] + M - temp)
                block[i][j] = (block[i][j-1] + val) % M
  • 最後步驟 :
    • 在主要程式碼中，由於我們是採用 Cumulative Sum (累積和) 運算方式，即 block[n][k-1] 中會多加個 block[n][k-1]，所以block[n][k] - block[n][k-1] 才是真正所求的值，回傳答案時也須額外注意 
      1
      2
      3
      4
      tem = 0
      if k > 0 :
          tem = block[n][k-1] # tem 為 前一格的值
      return (block[n][k] + M - tem) % M

參考資料

  1. 【演算法筆記系列 — Dynamic programming 動態規劃
  2. [LeetCode] K Inverse Pairs Array K个翻转对数组