在電腦科學的計算理論分支裡面，當今最值得關注的問題莫屬 P 等不等於 NP 的這個問題了。理論學家喜歡把問題歸類：能在多項式時間內解出來的題目被定義成一類 (P)、能夠在多項式時間內驗證一個答案是不是滿足題目的解被定義成另外一類 (NP)。顯然能在多項式時間內解出來題目都可以用多項式時間來驗證 (P ⊆ NP)。但是除此之外，世界上的人們仍不知道，是否所有在 NP 的題目都可以用多項式時間內被解決（抑或是，目前大家普遍相信，存在某個特定的題目，找不到多項式時間演算法來解它。）

自古以來（也沒有那麼古啦，是奠定計算理論基礎的 Stephen Cook 在 1971 年正式刻劃出 P vs NP 問題以後）一直有許多人嘗試去解決這個問題。https://www.win.tue.nl/~gwoegi/P-versus-NP.htm 這個網站蒐集了許多嘗試解決 P vs NP 問題的研究紀錄，很可惜地最後這些論文都沒辦法完全證明到底 P=NP 還是 P≠NP。而這個列表還在持續增加當中。

有趣的是，有一類問題被定義成 NP-完備問題 (NP-Complete)，而且只要能用多項式時間正確解決任何一個這群問題中的任何一個，那麼——能夠用計算理論證明出 P = NP！

我們今天來用動態規劃方法來解決其中幾個問題吧！

子集合之和問題 (Subset Sum to Target Problem)

給你 n 個正整數還有一個閾值 t，請問是否存在一個子集合，使得集合內數字總和恰好是 t？

思考過程

由於數值都是正整數，那麼這個問題使用背包問題 (Knapsack) 來解它。詳情請參考 Day 11。時間複雜度是 O(nt)。你可能會說，這複雜度看起來像是多項式呀！為什麼它不是多項式的解法呢？

原因是這樣的，當我們說一個演算法是「多項式時間」的演算法，是相對於輸入資料量的（輸入的總位元數）多項式。但是要表達 n 個正整數、以及正整數 t，輸入的總位元數大概是 O(n log t)，所以對 t 來說，我們執行時間反而是指數時間的，慘慘。

Exercise 25: Leetcode 494 - Target Sum

題目連結

https://leetcode.com/problems/target-sum/

題目敘述

給你 N 個非負整數以及一個目標數值 S，請問有幾種加正負號的方法，可以讓所有數字的總和恰好是 S 呢？

解題思考

這題可以直接轉換成子集合問題的思考方式：其實就是要找一個子集合加上正號，其他通通加負號，使得這個子集合的總和 t = (S + sum(a1...an)) / 2。

我們也可以直接用背包問題的概念來解這題：假設 dp(i, x) = 用前 i 個數值，加上正負號以後，湊出總和為 x 的方法數，一路做下去即可～。

參考程式碼 (Python3)

from collections import defaultdict

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        dp = defaultdict(int)
        dp[0] = 1
        for num in nums:
            nxt = defaultdict(int)
            for k, v in dp.items():
                nxt[k + num] += v
                nxt[k - num] += v
            dp = nxt
        return dp[S]

Exercise 26: Leetcode 956 - Tallest Billboard

題目連結

https://leetcode.com/problems/tallest-billboard/

題目敘述

給你 n 個正整數，請找到一個最大的正整數 t，使得存在兩個互斥的子集合，分別加總兩個子集合內的數字，它們會同時等於 t。

解題思考

我們可以循著背包問題的思路：當我們考慮了前 k 個數字以後，對於每個數字，我們可以把它丟到第一個集合、第二個集合、或是丟到垃圾桶。因此我們可以用 dp(k, s1, s2) = True or False 來表示是否能同時達到第一個集合總和 = s1、第二個集合總和 = s2。而要輸出的 t 值就會是能讓 dp(n, t, t) = True 的最大 t 值了。時間複雜度 n * s1 * s2。

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {}
        dp[(0, 0)] = 0
        for idx, rod in enumerate(rods):
            all_keys = list(dp.keys())
            for s1, s2 in all_keys:
                dp[(s1 + rod, s2)] = idx
                dp[(s1, s2 + rod)] = idx
        return max([t for t in range(0, sum(rods) // 2 + 1) if dp.get((t, t)) != None])

然後傳上去會 TLE。現在讓我們想想看，有沒有辦法換個方法來看這個問題。首先注意到的是我們動態規劃的值放的是 True 或 False，其實感覺很不經濟實惠——或許可以儲存更多資訊的。其次是，我們只關心最終 s1 = s2 的情形啊。所以其實有很多多餘的計算是不必要的呢。

哪些計算是不必要的呢？比方說我們看到 (s1, s2) = (5, 8) 與 (s1, s2) = (9, 12)，這兩者的差值都相同，顯然若有機會放入剩下的數字使得兩者總和相同時 (也就是說 s1+X = s2+Y)，選擇後者，最後獲得的總和保證會比較大 (9+X = 12+Y 樂勝 5+X = 8+Y)。

因此我們可以得到一點啟發，如果我們從頭到尾只紀錄 「s1 與 s2 的差值」作為狀態，那最後我們要找的所有狀態都會對應到 s1 - s2 = 0 的情形。也就是說：我們希望定義的 dp(k, s1-s2) = 能夠滿足 (s1, s2) 當中，使得總和盡可能大的 s1 最大值。

現在拿到一個數字 a[k]，以及差值 s，我們要怎麼獲得 dp(k, s = s1-s2) 的最大可能 s1 呢？有三種情形：a[k] 出現在第一堆、a[k] 出現在第二堆、或 a[k] 不出現。

• a[k] 出現在第一堆：
  那麼在 a[k] 加入之前，(s1, s2) 往回推得 (s1-a[k], s2)，因此我們要找的是 dp(k-1, s1-a[k]-s2) 這會給你最大的 s1'，我們把 a[k] 加回來就也會是最大的啦。
• a[k] 出現在第二堆：
  那麼在 a[k] 加入之前，(s1, s2) 往回推得 (s1, s2-a[k])，因此我們要找的是 dp(k-1, s1-s2+a[k]) 這會給你最大的 s1'，而且這個 s1' 就是最大的 s1。
• a[k] 不出現：
  答案當然是 dp(k-1, s1-s2) 的最大 s1。

從以上三種情形中，選最大的那個 s1，就是答案囉！

參考程式碼 (Python3)

from collections import defaultdict

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = defaultdict(lambda: float("-inf"))
        dp[0] = 0
        for rod in rods:
            nxt = defaultdict(lambda: float("-inf"))
            for diff in range(-2500, 2501):
                nxt[diff] = max(dp[diff - rod] + rod,     # Case 1
                                dp[diff + rod],           # Case 2
                                dp[diff])                 # Case 3
            dp = nxt
        return dp[0]

時間複雜度是 O(nt)，其中 t 是最大可能的答案（本題中是 2500）。

看到標題你一定以為我要講集合覆蓋問題、最大獨立集問題、還有漢米爾頓圈問題對吧？我下標題的時候也是這樣以為的（汗）那我們只好明天繼續用同一個標題XD