動態規劃和組合數

預備知識

• 組合數是從 個物品中選出 個的不同方法數。我們用 或 來表示它。它的計算公式是：

這裡 表示 的階乘，也就是 。
特別注意，，所以 。

組合數還有一個遞迴關係，可以幫助我們快速計算：

這個公式的意思是，如果我們要從 個物品中選出 個，我們可以先看第 個物品。如果我們不選它，那麼就相當於從前 個物品中選出 個，有 種方法。如果我們選它，那麼就相當於從前 個物品中選出 個，再加上第 個物品，有 種方法。兩種情況加起來就是所有的方法數。

解題思路

• 我們先用 nums 陣列建立一棵二元搜尋樹，它的根節點是 nums[0]。
• 然後我們把 nums 中比 nums[0] 小的數放在左子樹，比 nums[0] 大的數放在右子樹，並按照出現順序插入。
• 這樣我們就把問題分成了兩個子問題：如何重排左子樹和右子樹的元素，使得插入後的樹和原來的樹一樣。
• 我們用 表示以 為根節點的子樹的排列方法數。如果 的左右子節點分別是 和 ，那麼 就等於從 的所有子節點中選出 的子節點個數的組合數，乘以 和 。

所以我們有以下狀態轉移方程式：

這裡 是以 為根節點的子樹的元素個數， 是組合數。如果 的某個子樹為空，那麽對應的 值為 ， 值為 。

• 我們要對答案取模數 (mod)，所以不能直接用組合數的公式，因為它有除法。
• 我們可以用遞迴的方法算出所有需要的組合數 ，其中 。遞迴公式是 。
• 這樣我們就不用做除法，只用加法和乘法，就可以快速求出組合數。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：5143)

程式

import kotlin.math.min

class Solution {
    private val mod = 1_000_000_007UL
    fun numOfWays(nums: IntArray): Int {
        return recursive(nums.toList()).toInt() - 1
    }

    private val c = Array(1001) { ULongArray(1001) { 0UL } }

    private fun combine(m: Int, n: Int): ULong {
        return if (m == n || n == 0) 1UL
        else if (n == 1) m.toULong()
        else if (c[m][n] != 0UL) c[m][n]
        else ((combine(m - 1, n - 1) % mod + combine(m - 1, n) % mod) % mod).also {
            c[m][n] = it
        }
    }

    private fun recursive(nums: List<Int>): ULong {
        if (nums.size <= 1) return 1UL
        else {
            val root = nums[0]
            val leftList = mutableListOf<Int>()
            val rightList = mutableListOf<Int>()
            for (i in 1 until nums.size) {
                val num = nums[i]
                if (num < root) {
                    leftList.add(num)
                } else {
                    rightList.add(num)
                }
            }
            val left = recursive(leftList)
            val right = recursive(rightList)
            val min = min(leftList.size, rightList.size)
            return (left * (right * (combine(leftList.size + rightList.size, min) % mod) % mod) % mod)
        }
    }
}

複雜度分析

• 時間複雜度:

我們要做三件事：處理組合數、建立二元搜尋樹、動態規劃。

• 處理組合數需要 的時間，因為我們要用遞迴公式算出所有可能的組合數。
• 建立二元搜尋樹的時間取決於 nums 陣列的順序。如果 nums 是隨機的，那麼平均需要 的時間。如果 nums 是有序的，那麼最壞需要 的時間，因為二元搜尋樹會變成一條鏈。
• 動態規劃需要 的時間，因為我們只要遍歷一次二元搜尋樹就可以了。

所以總的時間複雜度是 。

• 空間複雜度:
  ，因為我們要存儲所有的組合數和二元搜尋樹的節點。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：5143)