演算法思維總綱 (Algorithmic Thinking)#

學完一堆資料結構與演算法之後，真正把高手和普通人區分開的，不是「背了多少招式」，而是面對一個陌生問題時的思考方式。這一節談的就是這套貫穿全書的思維方法。

人的思維 vs 計算機的思維#

人類天生擅長遞推：從小到大、自底向上、一步步往前推。但計算機更擅長遞迴：自頂向下、先看全局再拆解局部。

這兩種方向常常是矛盾的。很多人寫遞迴卡住，本質上是因為還在用「遞推」的腦袋去想「遞迴」的問題。

要從普通工程師升級成一流工程師，需要有意識地改造自己的思維方式——學會在「自底向上的遞推」與「自頂向下的遞迴」之間自由切換。這個轉換，是後面遞迴、分治、動態規劃各章共同的底層能力。

培養演算法直覺的三個準則#

拿到一道題，不要急著套模板。先依序問自己三個問題：

先找問題的「下界」#

「不管怎麼做，至少要花多少工作？」——這道題的答案如果至少要掃過所有資料，那下界就是 O(n)，你寫出 O(n) 解就可以收手了。下界思維讓你既不會在最優解上空轉，也能看出目前的解還有沒有優化空間。

（這點在複雜度分析裡有更完整的展開。）

檢查是否在做「無用功」#

效率提升的本質，幾乎都是消除重複或無用的計算。

• 一個 O(n²) 的解，往往是把每個元素重複掃了 n 次；
• 一個 O(n) 的解，是想辦法讓每個元素只被處理一次。

所以優化的第一問永遠是：「我是不是在重複計算同一件事？」——這也正是動態規劃用快取消除重疊子問題的核心動機。

試試「逆向思維」#

當正著想卡住時，把問題反過來：

• 把序列倒過來看；
• 先假設「答案的一部分已經知道了」，再回推其餘部分。

一個經典例子：求最大子區間和時，如果已知最大區間的左邊界，只要往右掃一遍就能定出右邊界。那左邊界怎麼來？把序列倒過來再掃一遍即可。一道題、正反兩遍掃描，就得到 O(n) 解——這就是逆向思維的威力。

這個「往右掃一遍就定出邊界」的直覺，落到程式碼上就是 Kadane 演算法：邊掃邊決定「要接續前面的區間，還是從當前元素重新開始」，一趟 O(n) 就求出答案。

fun maxSubArray(nums: IntArray): Int {
    var best = nums[0]      // 目前為止的全域最大和
    var current = nums[0]   // 以當前元素結尾的最大和

    for (i in 1 until nums.size) {
        // 逆向思維：接續前段，還是從 nums[i] 重新開始？
        current = maxOf(nums[i], current + nums[i])
        best = maxOf(best, current)
    }

    return best
}

把問題「抽象」成已知模型#

高明的科學家，往往是透過研究一個問題，順手解決了一大批問題。關鍵能力是看出不同問題之間的等價性：

• 看出「司機配乘客、讀者配新聞、關鍵詞配廣告」其實都是同一個二分圖最大配對問題；
• 看出「編輯距離」其實是網格上的最短路徑問題；
• 看出某個計數問題其實就是卡特蘭數。

各種看似不同的資料結構，在計算機科學上常常是等價的——研究透一種，就能變通解決其他。能把陌生問題「翻譯」成熟悉的模型，是演算法能力的最高層次。

小結#

這四步不是按表操課的公式，而是一種看問題的角度。它們會在遞迴、分治、貪心、動態規劃、圖論各章反覆出現——讀後面章節時，不妨時時回來對照。