您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

LeetCode 374 & 375 猜數字遊戲：二分查找與極小化極大動態規劃完整解析

編輯：PHP 相關知識

LeetCode 374 & 375 猜數字遊戲：二分查找與極小化極大動態規劃完整解析

兩題同源異解：374 考二分查找基礎與溢位陷阱，375 考極小化極大 + 區間動態規劃。本文從遞歸直觀理解推導至底-up DP，附完整代碼、複雜度分析、遞歸樹圖解。

374. Guess Number Higher or Lower

題目重述

範圍 [1, n]，呼叫 API guess(num) 返回：-1 (目標較小)、1 (目標較大)、0 (命中)
找到目標數字

核心：標準二分查找

/** 
 * Forward declaration of guess API.
 * @param  int $num   your guess
 * @return int        -1 if target < num, 1 if target > num, 0 if equal
 */
function guess(int $num): int {}

class Solution {
    public function guessNumber(int $n): int {
        $left = 1;
        $right = $n;
        
        while ($left <= $right) {
            // ⚠️ 關鍵：避免 (left + right) 溢位
            // PHP 整數無上限 (任意精度)，但其他語言必須注意
            $mid = $left + (($right - $left) >> 1);  // 位運算等同 /2
            
            $res = guess($mid);
            if ($res === 0) return $mid;
            if ($res === -1) {
                $right = $mid - 1;  // 目標在左側
            } else {
                $left = $mid + 1;   // 目標在右側
            }
        }
        return -1;  // 理論上不可達
    }
}

關鍵點

中間值計算：left + (right - left) / 2 防溢位 (C++/Java 必須)，PHP 任意精度整數無此問題，但保持好習慣
邊界收縮：right = mid - 1 / left = mid + 1，避免死循環
時間複雜度：O(log n)，空間 O(1)

375. Guess Number Higher or Lower II

題目重述

猜錯需支付 $x (猜的數字)
最壞情況下確保獲勝的**最小成本**
即：極小化極大 — 選擇策略使「最大可能損失」最小化

遞歸直觀理解

對區間 [start, end]，嘗試每個 x 作為猜測：

成本 = x + max(左子區間成本, 右子區間成本)
取所有 x 的**最小值**
基礎情況：start >= end 成本 0 (單一數字無需猜)

遞歸 + 備忘錄 (Top-down DP)

class Solution {
    private $memo = [];

    public function getMoneyAmount(int $n): int {
        return $this->dfs(1, $n);
    }

    private function dfs(int $start, int $end): int {
        if ($start >= $end) return 0;
        if (isset($this->memo[$start][$end])) return $this->memo[$start][$end];

        $minCost = PHP_INT_MAX;
        // 優化：只需嘗試中間偏左區間 (數學證明最優解在中間)
        for ($x = $start; $x <= $end; $x++) {
            $cost = $x + max($this->dfs($start, $x - 1), $this->dfs($x + 1, $end));
            $minCost = min($minCost, $cost);
        }
        return $this->memo[$start][$end] = $minCost;
    }
}

底-up 動態規劃 (Bottom-up DP) — 空間優化

class Solution {
    public function getMoneyAmount(int $n): int {
        // dp[i][j] 表示區間 [i, j] 的最小最大成本
        $dp = array_fill(0, $n + 2, array_fill(0, $n + 2, 0));

        // 長度從 2 到 n (長度 1 成本為 0，已初始化)
        for ($len = 2; $len <= $n; $len++) {
            for ($start = 1; $start + $len - 1 <= $n; $start++) {
                $end = $start + $len - 1;
                $dp[$start][$end] = PHP_INT_MAX;
                
                // 優化：x 只需遍歷到 (start+end)/2 附近 (對稱性)
                for ($x = $start; $x <= $end; $x++) {
                    $cost = $x + max($dp[$start][$x - 1], $dp[$x + 1][$end]);
                    $dp[$start][$end] = min($dp[$start][$end], $cost);
                }
            }
        }
        return $dp[1][$n];
    }
}

複雜度分析

版本	時間	空間	備註
遞歸 + 備忘錄	O(n³)	O(n²)	狀態 n²，每狀態遍歷 O(n)
Bottom-up DP	O(n³)	O(n²)	實際較快，無遞歸開銷
優化 (Knuth/Yao)	O(n²)	O(n²)	利用四邊形不等式/單調性，面試一般不要求

遞歸樹圖解 (n=3)

區間 [1,3] 嘗試 x=1,2,3:
x=1: cost = 1 + max(0, dp[2,3])
       dp[2,3]: x=2 → 2+max(0,0)=2; x=3 → 3+max(0,0)=3 → min=2
       總成本 = 1+2 = 3

x=2: cost = 2 + max(dp[1,1], dp[3,3]) = 2 + max(0,0) = 2  ⭐ 最優

x=3: cost = 3 + max(dp[1,2], 0)
       dp[1,2]: x=1 → 1; x=2 → 2 → min=1
       總成本 = 3+1 = 4

答案：2 (先猜 2，最壞支付 $2)

進階：最小化期望損失 (Follow-up)

若目標均勻分布，改為最小化期望值：

// 期望成本 = Σ P(target) * cost(path)
// 遞歸公式：
// E(start, end) = min_x [ x + (x-start)/(end-start+1)*E(start,x-1) + (end-x)/(end-start+1)*E(x+1,end) ]
// 基礎：E(i,i) = 0