2025年8月17日 星期日

《面試官問完，開AI回答》LeetCode PHP 問題集錦（進階篇二）

目錄

  • 動態規劃 (Dynamic Programming)

      1. 不同路徑 II (Unique Paths II)

      1. 不同的子序列 (Distinct Subsequences)

      1. 買賣股票的最佳時機 III (Best Time to Buy and Sell Stock III)

      1. 分割回文串 II (Palindrome Partitioning II)

      1. 單詞拆分 (Word Break)

      1. 買賣股票的最佳時機 IV (Best Time to Buy and Sell Stock IV)

      1. 打家劫舍 (House Robber)

      1. 打家劫舍 II (House Robber II)

      1. 完全平方數 (Perfect Squares)

      1. 最佳買賣股票時機含冷凍期 (Best Time to Buy and Sell Stock with Cooldown)

      1. 整數拆分 (Integer Break)

      1. 組合總和 IV (Combination Sum IV)

      1. 零錢兌換 II (Coin Change II)

      1. 兩個字串的刪除操作 (Delete Operation for Two Strings)

      1. 回文子串 (Palindromic Substrings)

      1. 最長遞增子序列的個數 (Number of Longest Increasing Subsequence)

      1. 最長連續遞增序列 (Longest Continuous Increasing Subsequence)

      1. 買賣股票的最佳時機含手續費 (Best Time to Buy and Sell Stock with Transaction Fee)

      1. 最長重複子陣列 (Maximum Length of Repeated Subarray)

      1. 使用最小花費爬樓梯 (Min Cost Climbing Stairs)

      1. 不相交的線 (Uncrossed Lines)

      1. 最後一塊石頭的重量 II (Last Stone Weight II)

0063. 不同路徑 II (Unique Paths II)

問題描述：一個機器人位於一個 m x n 網格的左上角。它只能向下或向右移動。網格中可能包含障礙物。求機器人從左上角到右下角的不同路徑數量。

正確解題思路概述：

這是在 0062. 不同路徑 基礎上的延伸。我們仍然可以使用動態規劃。定義 dp[i][j] 為從起點到網格 (i, j) 的路徑數量。

  • 狀態轉移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]。

  • 特殊處理：如果網格 (i][j] 是一個障礙物，則 dp[i][j] = 0。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);

        if ($obstacleGrid[0][0] === 1 || $obstacleGrid[$m - 1][$n - 1] === 1) {
            return 0;
        }

        $dp = array_fill(0, $m, array_fill(0, $n, 0));
        $dp[0][0] = 1;

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($obstacleGrid[$i][$j] === 1) {
                    $dp[$i][$j] = 0;
                    continue;
                }
                if ($i > 0) {
                    $dp[$i][$j] += $dp[$i - 1][$j];
                }
                if ($j > 0) {
                    $dp[$i][$j] += $dp[$i][$j - 1];
                }
            }
        }
        return $dp[$m - 1][$n - 1];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在處理邊界情況時存在嚴重的錯誤。

  • 錯誤點：$dp[0][0] = 1; 放在了迴圈外面，但在迴圈內部又對 $dp[i][j] 進行了累加。當 $i 和 $j 都為 0 時，$dp[0][0] 會被錯誤地再次加 0，然後如果遇到障礙物，它又會被錯誤地歸零。更重要的是，它沒有正確處理第一行和第一列的初始值。如果第一行或第一列有障礙物，其後續的格子都應該是不可達的。

正確的 PHP 解決方案 (Corrected PHP Solution)：

先初始化第一行和第一列，然後再進行動態規劃。

PHP
class Solution {
    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);

        if ($obstacleGrid[0][0] === 1) {
            return 0;
        }

        $dp = array_fill(0, $m, array_fill(0, $n, 0));
        $dp[0][0] = 1;

        // Initialize first column
        for ($i = 1; $i < $m; $i++) {
            $dp[$i][0] = ($obstacleGrid[$i][0] === 0) ? $dp[$i - 1][0] : 0;
        }
        
        // Initialize first row
        for ($j = 1; $j < $n; $j++) {
            $dp[0][$j] = ($obstacleGrid[0][j] === 0) ? $dp[0][$j - 1] : 0;
        }

        // Fill the rest of the DP table
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                if ($obstacleGrid[$i][$j] === 1) {
                    $dp[$i][$j] = 0;
                } else {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
                }
            }
        }

        return $dp[$m - 1][$n - 1];
    }
}

除錯本類問題的技巧：

  1. 動態規劃初始化：對於 DP 問題，邊界條件的初始化至關重要。第一行和第一列通常需要單獨處理。

  2. 狀態轉移方程：確保你的狀態轉移方程能夠正確地從子問題推導出當前問題。

0115. 不同的子序列 (Distinct Subsequences)

問題描述：給定兩個字串 s 和 t，求 s 中有多少個子序列等於 t。

正確解題思路概述：

這是一個二維動態規劃問題。定義 dp[i][j] 為 s 的前 i 個字元中包含 t 的前 j 個字元的子序列數量。

  • 狀態轉移方程：

    • 如果 s[i-1] == t[j-1]，則 dp[i][j] 有兩種情況：

      • 不使用 s[i-1] 來匹配 t[j-1]：數量為 dp[i-1][j]。

      • 使用 s[i-1] 來匹配 t[j-1]：數量為 dp[i-1][j-1]。

      • 所以 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。

    • 如果 s[i-1] != t[j-1]，則 s[i-1] 不能用來匹配 t[j-1]：

      • dp[i][j] = dp[i-1][j]。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Integer
     */
    function numDistinct($s, $t) {
        $m = strlen($s);
        $n = strlen($t);

        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

        for ($i = 0; $i <= $m; $i++) {
            $dp[$i][0] = 1;
        }
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($s[$i - 1] === $t[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i - 1][$j - 1];
                } else {
                    $dp[$i][$j] = $dp[$i - 1][$j];
                }
            }
        }

        return $dp[$m][$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯和實現都是正確的，沒有明顯的邏輯錯誤。它的問題在於，如果 s 和 t 的長度非常大，它會導致記憶體超限。

  • 錯誤點：這不是一個邏輯錯誤，而是一個效能問題。它使用了 O(mcdotn) 的空間複雜度，這對於大規模輸入來說是不可接受的。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用空間優化的動態規劃。由於 dp[i][j] 只依賴於 dp[i-1][...]，我們可以將二維陣列壓縮成一維陣列。

PHP
class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Integer
     */
    function numDistinct($s, $t) {
        $m = strlen($s);
        $n = strlen($t);

        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 1;

        for ($i = 1; $i <= $m; $i++) {
            for ($j = $n; $j >= 1; $j--) {
                if ($s[$i - 1] === $t[$j - 1]) {
                    $dp[$j] = $dp[$j] + $dp[$j - 1];
                }
            }
        }
        
        return $dp[$n];
    }
}

除錯本類問題的技巧：

  1. 空間複雜度：對於二維 DP，如果 dp[i][j] 只依賴於 i-1 的狀態，通常可以將空間複雜度從 O(mcdotn) 降至 O(n)。

  2. 滾動陣列：當使用一維陣列優化二維 DP 時，要特別注意迴圈的方向。為了不影響當前計算所需的 dp[j-1] 舊值，內層迴圈通常需要從後往前遍歷。

0123. 買賣股票的最佳時機 III (Best Time to Buy and Sell Stock III)

問題描述：最多可以完成兩次交易，求能獲得的最大利潤。

正確解題思路概述：

這是一個複雜的動態規劃問題，可以分為兩種方法：

  1. 四個狀態機：buy1, sell1, buy2, sell2。

    • buy1[i]：在第 i 天結束時，第一次買入後手頭的現金。

    • sell1[i]：在第 i 天結束時，第一次賣出後手頭的現金。

    • buy2[i]：在第 i 天結束時，第二次買入後手頭的現金。

    • sell2[i]：在第 i 天結束時，第二次賣出後手頭的現金。

    • 狀態轉移方程：buy1 = max(buy1, -price), sell1 = max(sell1, buy1 + price), buy2 = max(buy2, sell1 - price), sell2 = max(sell2, buy2 + price).

  2. 分治法：將陣列在某一點 i 分割成兩部分 [0, i] 和 [i+1, n-1]，分別計算這兩部分的單次最大利潤，然後相加。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $n = count($prices);
        if ($n < 2) {
            return 0;
        }

        $profit = 0;
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                $profit1 = 0;
                for ($k = 0; $k <= $i; $k++) {
                    $profit1 = max($profit1, $prices[$i] - $prices[$k]);
                }
                $profit2 = 0;
                for ($l = $j; $l < $n; $l++) {
                    $profit2 = max($profit2, $prices[$l] - $prices[$j]);
                }
                $profit = max($profit, $profit1 + $profit2);
            }
        }
        return $profit;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼採用了最暴力的暴力枚舉方法。

  • 錯誤點：它嘗試枚舉所有可能的兩次交易的組合。時間複雜度是 O(N4)，這在面臨大規模輸入時會超時。它雖然邏輯正確，但完全沒有利用動態規劃的思想，因此不是一個有效的解法。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用四個狀態機的動態規劃方法。

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $buy1 = PHP_INT_MIN;
        $sell1 = 0;
        $buy2 = PHP_INT_MIN;
        $sell2 = 0;
        
        foreach ($prices as $price) {
            $buy1 = max($buy1, -$price);
            $sell1 = max($sell1, $buy1 + $price);
            $buy2 = max($buy2, $sell1 - $price);
            $sell2 = max($sell2, $buy2 + $price);
        }
        
        return $sell2;
    }
}

除錯本類問題的技巧：

  1. 狀態定義：複雜的 DP 問題，關鍵在於如何定義狀態。對於買賣股票，將「手頭現金」和「交易次數」作為狀態是常見的模式。

  2. 狀態壓縮：由於當前狀態只依賴於前一天的狀態，我們可以將空間複雜度從 O(N) 降至 O(1)。

  3. 避免暴力枚舉：對於任何帶有「最大/最小」和「子問題」特徵的問題，首先思考是否可以用 DP 來優化。

0132. 分割回文串 II (Palindrome Partitioning II)

問題描述：將一個字串分割成若干個回文子字串，求最少分割次數。

正確解題思路概述：

這是一個動態規劃問題。定義 dp[i] 為字串的前 i 個字元最少需要的分割次數。

  • 狀態轉移方程：dp[i] = min(dp[j] + 1)，其中 0 <= j < i，且從 j 到 i-1 的子字串是回文串。

  • 預處理：為了快速判斷一個子字串是否為回文，我們可以用一個二維 DP 陣列 isPalindrome[i][j] 來預處理。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function minCut($s) {
        $n = strlen($s);
        if ($n <= 1) {
            return 0;
        }

        $minCut = $n - 1;
        
        function isPalindrome($str) {
            return $str === strrev($str);
        }
        
        function solve($s, $cuts) {
            if (isPalindrome($s)) {
                return $cuts;
            }
            
            $minCuts = PHP_INT_MAX;
            for ($i = 1; $i < strlen($s); $i++) {
                $prefix = substr($s, 0, $i);
                $suffix = substr($s, $i);
                if (isPalindrome($prefix)) {
                    $minCuts = min($minCuts, solve($suffix, $cuts + 1));
                }
            }
            return $minCuts;
        }

        return solve($s, 0);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼使用了遞歸回溯方法，存在嚴重的超時問題。

  • 錯誤點：它沒有利用動態規劃來避免重複計算。在遞歸過程中，很多子問題（例如 solve($suffix)）會被重複計算。例如，abcba 和 abcab 都會計算 ab 的子問題。這種暴力回溯的複雜度極高。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用動態規劃。

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function minCut($s) {
        $n = strlen($s);
        if ($n <= 1) {
            return 0;
        }

        // DP table for palindromes
        $isPalindrome = array_fill(0, $n, array_fill(0, $n, false));
        for ($i = 0; $i < $n; $i++) {
            $isPalindrome[$i][$i] = true;
        }
        for ($len = 2; $len <= $n; $len++) {
            for ($i = 0; $i <= $n - $len; $i++) {
                $j = $i + $len - 1;
                if ($s[$i] === $s[$j]) {
                    if ($len === 2 || $isPalindrome[$i + 1][$j - 1]) {
                        $isPalindrome[$i][$j] = true;
                    }
                }
            }
        }

        // DP table for minimum cuts
        $dp = array_fill(0, $n, 0);
        for ($i = 0; $i < $n; $i++) {
            if ($isPalindrome[0][$i]) {
                $dp[$i] = 0;
            } else {
                $dp[$i] = $i;
                for ($j = 0; $j < $i; $j++) {
                    if ($isPalindrome[$j + 1][$i]) {
                        $dp[$i] = min($dp[$i], $dp[$j] + 1);
                    }
                }
            }
        }
        return $dp[$n - 1];
    }
}

除錯本類問題的技巧：

  1. 預處理：當一個子問題（如「是否為回文」）被重複查詢時，考慮用預處理來儲存結果，這通常是 DP 的一種形式。

  2. 遞歸 vs. DP：如果遞歸過程中存在重複子問題，這是一個強烈的信號，表明應該使用 DP 或帶有記憶化的遞歸。

0139. 單詞拆分 (Word Break)

問題描述：給定一個非空字串 s 和一個包含非空單詞的字典 wordDict，判斷 s 是否可以被拆分為一個或多個在字典中的單詞。

正確解題思路概述：

這是一個動態規劃問題。定義 dp[i] 為字串的前 i 個字元是否可以被成功拆分。

  • 狀態轉移方程：dp[i] = dp[j] && (s[j...i-1] in wordDict)，其中 0 <= j < i。也就是說，如果字串 s 的前 i 個字元可以被拆分，那麼它一定存在一個分割點 j，使得 s 的前 j 個字元可以被拆分，且從 j 到 i-1 的子字串在字典中。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @param String[] $wordDict
     * @return Boolean
     */
    function wordBreak($s, $wordDict) {
        $memo = [];
        return $this->canBreak($s, $wordDict, $memo);
    }

    private function canBreak($s, $wordDict, &$memo) {
        if ($s === "") {
            return true;
        }
        if (isset($memo[$s])) {
            return $memo[$s];
        }

        foreach ($wordDict as $word) {
            if (strpos($s, $word) === 0) {
                if ($this->canBreak(substr($s, strlen($word)), $wordDict, $memo)) {
                    $memo[$s] = true;
                    return true;
                }
            }
        }
        
        $memo[$s] = false;
        return false;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼採用了帶有記憶化的遞歸，邏輯上是正確的。但它的效能和程式碼風格存在問題。

  • 錯誤點：strpos($s, $word) === 0 這行是錯誤的。它只會檢查字典中的單詞是否是當前字串的前綴，但它沒有考慮所有可能的分割點。正確的邏輯應該是枚舉所有可能的分割點，然後檢查分割點前的字串是否可拆分，以及分割點後的字串是否在字典中。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用自底向上的動態規劃方法。

PHP
class Solution {
    /**
     * @param String $s
     * @param String[] $wordDict
     * @return Boolean
     */
    function wordBreak($s, $wordDict) {
        $n = strlen($s);
        $wordDict = array_flip($wordDict);
        $dp = array_fill(0, $n + 1, false);
        $dp[0] = true;

        for ($i = 1; $i <= $n; $i++) {
            for ($j = 0; $j < $i; $j++) {
                if ($dp[$j] && isset($wordDict[substr($s, $j, $i - $j)])) {
                    $dp[$i] = true;
                    break;
                }
            }
        }

        return $dp[$n];
    }
}

除錯本類問題的技巧：

  1. 狀態定義：清晰地定義 dp[i] 的含義。

  2. 枚舉分割點：對於字串分割問題，枚舉所有可能的分割點是標準的 DP 模式。

0188. 買賣股票的最佳時機 IV (Best Time to Buy and Sell Stock IV)

問題描述：最多可以完成 k 次交易，求能獲得的最大利潤。

正確解題思路概述：

這是買賣股票系列的泛化版本。這是一個三維動態規劃問題，或者可以優化為二維。

  • 狀態定義：dp[i][j][0] 和 dp[i][j][1]，分別代表在第 i 天，完成了 j 次交易，手頭是否持有股票的最大利潤。

    • dp[i][j][0]：第 i 天，完成了 j 次交易，手頭沒有股票。

    • dp[i][j][1]：第 i 天，完成了 j 次交易，手頭持有股票。

  • 狀態轉移方程：

    • dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]) (賣出或維持)

    • dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) (買入或維持)

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($k, $prices) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        if ($k >= $n / 2) {
            $profit = 0;
            for ($i = 1; $i < $n; $i++) {
                if ($prices[$i] > $prices[$i - 1]) {
                    $profit += $prices[$i] - $prices[$i - 1];
                }
            }
            return $profit;
        }
        
        $dp = array_fill(0, $k + 1, array_fill(0, 2, 0));

        // Initialize buy states
        for ($j = 1; $j <= $k; $j++) {
            $dp[$j][1] = -$prices[0];
        }

        for ($i = 1; $i < $n; $i++) {
            for ($j = 1; $j <= $k; $j++) {
                $buy = $dp[$j][1];
                $sell = $dp[$j][0];
                
                $dp[$j][0] = max($sell, $buy + $prices[$i]);
                $dp[$j][1] = max($buy, $dp[$j-1][0] - $prices[$i]);
            }
        }
        return $dp[$k][0];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但存在一個細微的實現錯誤。

  • 錯誤點：在內層迴圈中，它使用了 $dp[$j][0] = max($sell, $buy + $prices[$i]); 和 $dp[$j][1] = max($buy, $dp[$j-1][0] - $prices[$i]);。這裡的 $buy 和 $sell 變數在每次內層迴圈中都會被覆蓋，但它們應該是上一次迴圈的結果。這導致了錯誤的計算。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用兩個一維陣列來儲存 dp[j][0] 和 dp[j][1]，或使用四個變數來實現空間優化。

PHP
class Solution {
    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($k, $prices) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        if ($k >= $n / 2) {
            // Equivalent to max profit with infinite transactions
            $profit = 0;
            for ($i = 1; $i < $n; $i++) {
                if ($prices[$i] > $prices[$i - 1]) {
                    $profit += $prices[$i] - $prices[$i - 1];
                }
            }
            return $profit;
        }
        
        // DP with O(k) space
        $buy = array_fill(0, $k + 1, PHP_INT_MIN);
        $sell = array_fill(0, $k + 1, 0);

        foreach ($prices as $price) {
            for ($j = 1; $j <= $k; $j++) {
                $buy[$j] = max($buy[$j], $sell[$j - 1] - $price);
                $sell[$j] = max($sell[$j], $buy[$j] + $price);
            }
        }
        
        return $sell[$k];
    }
}

除錯本類問題的技巧：

  1. 狀態更新：在動態規劃中，如果你使用空間優化，確保你使用的舊值是正確的。在這種情況下，使用兩個獨立的陣列或臨時變數來儲存上一步的狀態。

  2. 特殊情況：如果 k 足夠大，問題會退化為「無限次交易」的情況，此時可以應用一個更簡單的貪心演算法來優化。

0198. 打家劫舍 (House Robber)

問題描述：你是一個專業的竊賊，計畫沿著一條街打劫。每間房屋都有一定的金錢，唯一會觸動警報的限制是，相鄰的房屋不能同時被竊取。求在不觸動警報的情況下，能竊取的最大金額。

正確解題思路概述：

這是一個經典的動態規劃問題。定義 dp[i] 為考慮到第 i 間房屋時，能竊取的最大金額。

  • 狀態轉移方程：

    • 竊取第 i 間房屋：dp[i] = nums[i] + dp[i-2]。

    • 不竊取第 i 間房屋：dp[i] = dp[i-1]。

    • 最終 dp[i] = max(nums[i] + dp[i-2], dp[i-1])。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $nums[0];
        }

        $dp = array_fill(0, $n, 0);
        $dp[0] = $nums[0];
        $dp[1] = $nums[1]; // 錯誤點

        for ($i = 2; $i < $n; $i++) {
            $dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
        }
        return $dp[$n - 1];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼在初始化 dp 陣列時存在一個邏輯錯誤。

  • 錯誤點：$dp[1] = $nums[1]; 是錯誤的。對於第二間房屋，最大金額應該是選擇第一間 (nums[0]) 還是第二間 (nums[1]) 中金額較大的那個，而不是簡單地選擇第二間。例如 [2, 1, 1, 2]，dp[0]=2，dp[1] 如果初始化為 1，後續計算會出錯。正確的 dp[1] 應該是 max(nums[0], nums[1])。

  • 另一個潛在錯誤：這段程式碼沒有考慮到 DP 陣列的空間優化。dp[i] 只依賴於 dp[i-1] 和 dp[i-2]，因此可以將空間複雜度從 O(N) 降至 O(1)。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用空間優化的動態規劃方法。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $nums[0];
        }

        $prev2 = 0; // Represents dp[i-2]
        $prev1 = 0; // Represents dp[i-1]

        foreach ($nums as $num) {
            $current = max($prev1, $prev2 + $num);
            $prev2 = $prev1;
            $prev1 = $current;
        }
        return $prev1;
    }
}

除錯本類問題的技巧：

  1. 初始值：確保動態規劃陣列的初始值設置正確，這通常是邊界情況的答案。

  2. 狀態壓縮：當 dp[i] 只依賴於前幾個狀態時，考慮用幾個變數來代替整個 DP 陣列，以節省空間。

0213. 打家劫舍 II (House Robber II)

問題描述：與打家劫舍 I 相同，但房屋是圍成一圈的。這意味著第一間房屋和最後一間房屋是相鄰的。

正確解題思路概述：

由於第一間和最後一間不能同時打劫，我們可以將這個環形問題分解為兩個非環形的打家劫舍 I 問題：

  1. 不打劫最後一間房屋：在 nums[0...n-2] 範圍內求解。

  2. 不打劫第一間房屋：在 nums[1...n-1] 範圍內求解。

    最終答案是這兩個子問題解的最大值。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $nums[0];
        }

        // Case 1: Robbing the first house
        $result1 = $this->robSub($nums, 0, $n - 2);

        // Case 2: Robbing the last house
        $result2 = $this->robSub($nums, 1, $n - 1);

        return max($result1, $result2);
    }
    
    private function robSub($nums, $start, $end) {
        $prev2 = 0;
        $prev1 = 0;

        for ($i = $start; $i <= $end; $i++) {
            $current = max($prev1, $prev2 + $nums[$i]);
            $prev2 = $prev1;
            $prev1 = $current;
        }
        return $prev1;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但它在處理只有兩間房屋的特殊情況時會出錯。

  • 錯誤點：當 n=2 時，$this->robSub($nums, 0, 0) 和 $this->robSub($nums, 1, 1) 會被呼叫。robSub 函數在只有一個元素時是正確的，但當 n=2 時，robSub($nums, 0, 0) 會返回 nums[0]，robSub($nums, 1, 1) 會返回 nums[1]，最終返回 max(nums[0], nums[1])。這似乎是正確的。然而，如果 n=3，robSub(..., 0, 1) 和 robSub(..., 1, 2)，這也是正確的。

  • 真正的潛在錯誤：這段程式碼沒有處理 n=0 或 n=1 的情況，雖然主函數處理了。當 n=1 時，robSub($nums, 0, -1) 會被呼叫，這會導致錯誤。雖然主函數中的 if ($n === 1) 處理了，但這說明子函數的健壯性不足。

正確的 PHP 解決方案 (Corrected PHP Solution)：

在主函數中處理邊界情況，並確保子函數的輸入範圍是有效的。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $nums[0];
        }

        // Case 1: Exclude the last house
        $result1 = $this->robSub(array_slice($nums, 0, $n - 1));

        // Case 2: Exclude the first house
        $result2 = $this->robSub(array_slice($nums, 1, $n - 1));

        return max($result1, $result2);
    }
    
    private function robSub($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        $prev2 = 0;
        $prev1 = 0;

        foreach ($nums as $num) {
            $current = max($prev1, $prev2 + $num);
            $prev2 = $prev1;
            $prev1 = $current;
        }
        return $prev1;
    }
}

除錯本類問題的技巧：

  1. 環形分解：當問題是環形結構時，考慮將其分解為非環形的子問題。

  2. 子函數的健壯性：確保你設計的輔助函數能夠處理所有可能的輸入，包括空陣列或單元素陣列。

0279. 完全平方數 (Perfect Squares)

問題描述：給定一個正整數 n，求最少需要多少個完全平方數（例如 1, 4, 9, 16, ...）的和等於 n。

正確解題思路概述：

這是一個完全背包問題的變種。定義 dp[i] 為和為 i 的最少完全平方數數量。

  • 狀態轉移方程：dp[i] = min(dp[i - j*j] + 1)，其中 j*j 小於等於 i。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function numSquares($n) {
        $dp = array_fill(0, $n + 1, PHP_INT_MAX);
        $dp[0] = 0;

        $squares = [];
        for ($i = 1; $i * $i <= $n; $i++) {
            $squares[] = $i * $i;
        }

        for ($i = 1; $i <= $n; $i++) {
            foreach ($squares as $square) {
                if ($i >= $square) {
                    if ($dp[$i - $square] !== PHP_INT_MAX) {
                        $dp[$i] = min($dp[$i], $dp[$i - $square] + 1);
                    }
                }
            }
        }
        return $dp[$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯和實現都是正確的。它是一個標準的完全背包問題解法。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。在 PHP 中，PHP_INT_MAX 是一個合適的初始值。它正確地實現了狀態轉移方程，並利用了完全平方數的列表。

正確的 PHP 解決方案 (Corrected PHP Solution)：

這段程式碼本身就是一個正確的解決方案。我們不需要修正，但可以稍微改進其可讀性。

PHP
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function numSquares($n) {
        $dp = array_fill(0, $n + 1, PHP_INT_MAX);
        $dp[0] = 0;

        for ($i = 1; $i <= $n; $i++) {
            for ($j = 1; $j * $j <= $i; $j++) {
                $square = $j * $j;
                if ($dp[$i - $square] !== PHP_INT_MAX) {
                    $dp[$i] = min($dp[$i], $dp[$i - $square] + 1);
                }
            }
        }
        return $dp[$n];
    }
}

除錯本類問題的技巧：

  1. 問題抽象：將問題抽象為完全背包問題或零錢兌換問題是解決這類 DP 問題的關鍵。

  2. 初始值：確保你的 DP 陣列初始值能夠正確地處理無解的情況（PHP_INT_MAX）和基線情況 (dp[0] = 0)。

0309. 最佳買賣股票時機含冷凍期 (Best Time to Buy and Sell Stock with Cooldown)

問題描述：最多可以完成無限次交易，但每次賣出股票後，你必須等待一天才能再次買入。

正確解題思路概述：

這是一個帶有額外狀態的動態規劃問題。我們需要額外的狀態來追蹤「冷凍期」。

  • 狀態定義：

    • hold[i]：在第 i 天結束時，手頭持有股票的最大利潤。

    • sold[i]：在第 i 天結束時，賣出股票後的最大利潤。

    • rest[i]：在第 i 天結束時，處於非交易狀態（休息或冷凍期）的最大利潤。

  • 狀態轉移方程：

    • hold[i] = max(hold[i-1], rest[i-1] - price)

    • sold[i] = hold[i-1] + price

    • rest[i] = max(rest[i-1], sold[i-1])

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        $buy = -$prices[0];
        $sell = 0;
        $cooldown = 0;

        for ($i = 1; $i < $n; $i++) {
            $prevBuy = $buy;
            $prevSell = $sell;
            $prevCooldown = $cooldown;

            $buy = max($prevBuy, $cooldown - $prices[$i]);
            $sell = $prevBuy + $prices[$i];
            $cooldown = max($prevCooldown, $prevSell);
        }
        return max($sell, $cooldown);
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯在狀態更新時存在一個細微的錯誤。

  • 錯誤點：$sell = $prevBuy + $prices[$i]; 是錯誤的。它沒有考慮到 sell 狀態也應該是 max 函數的結果，因為你可能選擇不賣出。

  • 更重要的錯誤：在狀態轉移方程中，$buy = max($prevBuy, $cooldown - $prices[$i]); 和 $cooldown = max($prevCooldown, $prevSell); 是正確的。但 $sell = $prevBuy + $prices[$i]; 只表示你賣出了股票，這是一個非最佳的選擇。它應該是 max($prevSell, $prevBuy + $prices[$i])。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用正確的狀態轉移方程。

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        $hold = PHP_INT_MIN;
        $sold = 0;
        $rest = 0;

        foreach ($prices as $price) {
            $prevHold = $hold;
            $prevSold = $sold;
            $prevRest = $rest;

            $hold = max($prevHold, $prevRest - $price);
            $sold = $prevHold + $price;
            $rest = max($prevRest, $prevSold);
        }
        return max($sold, $rest);
    }
}

除錯本類問題的技巧：

  1. 狀態定義：仔細定義每個狀態的含義，並思考其之間的依賴關係。

  2. 獨立變數：在更新狀態時，使用獨立的臨時變數來儲存前一個狀態的值，以避免混淆。

0343. 整數拆分 (Integer Break)

問題描述：給定一個正整數 n，將其拆分為至少兩個正整數的和，使這些整數的乘積最大化。

正確解題思路概述：

這是一個動態規劃問題。定義 dp[i] 為將 i 拆分後能得到的最大乘積。

  • 狀態轉移方程：dp[i] = max(j * (i - j), j * dp[i - j])，其中 1 <= j < i。

  • 數學優化：當 n >= 4 時，將其拆分為 2 和 3 會得到更好的結果。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function integerBreak($n) {
        if ($n === 2) {
            return 1;
        }
        if ($n === 3) {
            return 2;
        }

        $dp = array_fill(0, $n + 1, 0);
        $dp[1] = 1;
        $dp[2] = 2; // 錯誤點
        $dp[3] = 3; // 錯誤點

        for ($i = 4; $i <= $n; $i++) {
            $maxVal = 0;
            for ($j = 1; $j <= $i / 2; $j++) {
                $maxVal = max($maxVal, $j * $dp[$i - $j]);
            }
            $dp[$i] = $maxVal;
        }
        return $dp[$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼在初始化和狀態轉移方程上都存在錯誤。

  • 錯誤點：

    • dp[2] = 2; 和 dp[3] = 3; 是錯誤的。dp[i] 代表的是「最大乘積」，而不是 i 本身。2 的最大乘積是 1 * 1 = 1，3 的最大乘積是 1 * 2 = 2。

    • 狀態轉移方程 $j * $dp[$i - $j] 只考慮了拆分後的一部分繼續拆分，而忽略了 j * (i - j) 這個可能性。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用正確的初始值和狀態轉移方程。

PHP
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function integerBreak($n) {
        $dp = array_fill(0, $n + 1, 0);
        $dp[1] = 1;

        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j < $i; $j++) {
                $dp[$i] = max($dp[$i], $j * ($i - $j), $j * $dp[$i - $j]);
            }
        }
        return $dp[$n];
    }
}

除錯本類問題的技巧：

  1. 基線情況：對於 DP，明確定義基線情況的初始值。

  2. 全面性：確保你的狀態轉移方程考慮了所有可能的情況。在這個問題中，兩種情況都需要考慮：j 不再拆分，或 j 繼續拆分。

0377. 組合總和 IV (Combination Sum IV)

問題描述：給定一個由正整數組成的不同陣列 nums 和一個正整數 target。求所有可能的組合總數，其中可以重複使用 nums 中的數字。

正確解題思路概述：

這是一個完全背包問題的變種。定義 dp[i] 為和為 i 的組合總數。

  • 狀態轉移方程：dp[i] = sum(dp[i - num])，其中 num 在 nums 中。

    這個問題是排列數，而不是組合數，所以內層迴圈應該是 nums。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function combinationSum4($nums, $target) {
        $dp = array_fill(0, $target + 1, 0);
        $dp[0] = 1;
        
        foreach ($nums as $num) {
            for ($i = $num; $i <= $target; $i++) {
                $dp[$i] += $dp[$i - $num];
            }
        }
        return $dp[$target];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，它計算的是組合數，而不是排列數。

  • 錯誤點：外層迴圈是 nums，內層是 target。這種寫法會把 (1, 2) 和 (2, 1) 視為同一個組合。

  • 舉例：nums = [1, 2], target = 3。

    • 當 num = 1 時，dp[1]+=dp[0], dp[2]+=dp[1], dp[3]+=dp[2]。

    • 當 num = 2 時，dp[2]+=dp[0], dp[3]+=dp[1]。

    • 最終 dp[3] = (1,1,1) + (1,2) + (2,1)。這是不對的。dp[3] 的計算過程中，(1,2) 和 (2,1) 被視為同一個，這會導致結果錯誤。

正確的 PHP 解決方案 (Corrected PHP Solution)：

交換迴圈順序，先遍歷 target，再遍歷 nums，這樣就可以計算排列數。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function combinationSum4($nums, $target) {
        $dp = array_fill(0, $target + 1, 0);
        $dp[0] = 1;
        
        for ($i = 1; $i <= $target; $i++) {
            foreach ($nums as $num) {
                if ($i >= $num) {
                    $dp[$i] += $dp[$i - $num];
                }
            }
        }
        return $dp[$target];
    }
}

除錯本類問題的技巧：

  1. 排列 vs. 組合：對於背包問題，仔細區分是要求排列數還是組合數。

    • 排列數：先遍歷背包容量，再遍歷物品。

    • 組合數：先遍歷物品，再遍歷背包容量。

0416. 分割等和子集 (Partition Equal Subset Sum)

問題描述：給你一個只包含正整數的非空陣列 nums，判斷是否可以將其分割成兩個子集，使得兩個子集的元素和相等。

正確解題思路概述：

這是一個經典的0-1 背包問題。如果一個陣列可以被分割成兩個和相等的子集，那麼每個子集的和都必須是整個陣列總和的一半。因此，問題可以轉換為：是否能從 nums 中選出一些數字，使它們的總和恰好等於 sum(nums) / 2。

  • 狀態定義：dp[i] 表示是否可以從給定的數字中，湊出總和為 i。

  • 狀態轉移方程：dp[i] = dp[i] || dp[i - num]，其中 num 是 nums 中的一個數字。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canPartition($nums) {
        $sum = array_sum($nums);
        if ($sum % 2 !== 0) {
            return false;
        }
        $target = $sum / 2;
        
        $dp = array_fill(0, $target + 1, false);
        $dp[0] = true;
        
        foreach ($nums as $num) {
            for ($i = 0; $i <= $target; $i++) {
                if ($i >= $num) {
                    $dp[$i] = $dp[$i] || $dp[$i - $num];
                }
            }
        }
        
        return $dp[$target];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，它實現的是完全背包，而不是0-1 背包。

  • 錯誤點：內層迴圈 for ($i = 0; $i <= $target; $i++) 的方向是從前往後。這會導致同一個數字 num 被多次使用，例如當 nums = [1, 2] 時，num = 1 被處理後，dp[2] 會從 dp[1] 更新，而 dp[1] 是由 num = 1 更新的。這相當於使用了兩次 num=1，違背了每個數字只能用一次的 0-1 背包規則。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將內層迴圈的方向改為從後往前遍歷。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canPartition($nums) {
        $sum = array_sum($nums);
        if ($sum % 2 !== 0) {
            return false;
        }
        $target = $sum / 2;
        
        $dp = array_fill(0, $target + 1, false);
        $dp[0] = true;
        
        foreach ($nums as $num) {
            for ($i = $target; $i >= $num; $i--) {
                $dp[$i] = $dp[$i] || $dp[$i - $num];
            }
        }
        
        return $dp[$target];
    }
}

除錯本類問題的技巧：

  1. 區分背包問題：對於 0-1 背包，因為每個物品只能用一次，所以內層迴圈必須從後往前遍歷，以確保每個狀態 dp[i] 的更新只依賴於上一個物品的結果。

  2. 問題轉換：將一個看起來不像背包問題的問題，巧妙地轉換為背包問題是解題的關鍵。

0474. 一和零 (Ones and Zeros)

問題描述：給定一個由字串 strs 組成的陣列，每個字串只包含 0 和 1。再給定兩個整數 m 和 n，求 strs 的子集中，最多能有多少個字串，使得它們總共包含的 0 的數量不超過 m，總共包含的 1 的數量不超過 n。

正確解題思路概述：

這是一個多維度的0-1 背包問題。我們需要一個二維的 DP 陣列來追蹤 0 和 1 的數量。

  • 狀態定義：dp[i][j] 表示使用 i 個 0 和 j 個 1 時，最多能組成的字串數量。

  • 狀態轉移方程：對於每個字串 str，假設它有 zeros 個 0 和 ones 個 1，我們從後往前更新 DP 陣列：dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String[] $strs
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function findMaxForm($strs, $m, $n) {
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        foreach ($strs as $str) {
            $zeros = substr_count($str, '0');
            $ones = strlen($str) - $zeros;
            
            for ($i = 0; $i <= $m; $i++) {
                for ($j = 0; $j <= $n; $j++) {
                    if ($i >= $zeros && $j >= $ones) {
                        $dp[$i][$j] = max($dp[$i][$j], $dp[$i - $zeros][$j - $ones] + 1);
                    }
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，它實現的是完全背包。

  • 錯誤點：與上一個問題類似，內層迴圈 for ($i = 0; ...) 和 for ($j = 0; ...) 的方向都是從前往後。這會導致同一個字串被重複使用。例如，如果 strs = ["1", "1"]，m=2, n=2，它會錯誤地認為可以使用兩個 "1" 來組成一個解。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將兩個內層迴圈的方向都改為從後往前遍歷。

PHP
class Solution {
    /**
     * @param String[] $strs
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function findMaxForm($strs, $m, $n) {
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        foreach ($strs as $str) {
            $zeros = substr_count($str, '0');
            $ones = strlen($str) - $zeros;
            
            for ($i = $m; $i >= $zeros; $i--) {
                for ($j = $n; $j >= $ones; $j--) {
                    $dp[$i][$j] = max($dp[$i][$j], $dp[$i - $zeros][$j - $ones] + 1);
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯本類問題的技巧：

  1. 多維度背包：將多個約束條件（如 0 的數量和 1 的數量）映射到 DP 陣列的多個維度上。

  2. 0-1 背包：再次強調，當每個物品只能使用一次時，內層迴圈必須從後往前遍歷。

0494. 目標和 (Target Sum)

問題描述：給定一個非負整數陣列 nums 和一個目標 target。你可以在每個數字前加上 + 或 -，然後串聯所有數字來構造一個表達式。求有多少種不同的表達式，其結果等於 target。

正確解題思路概述：

這是一個轉換為背包問題的動態規劃。

假設所有加上 + 的數字和為 P，所有加上 - 的數字和為 N。

則 P - N = target。

我們知道 P + N = sum(nums)。

將兩式相加，得到 2P = target + sum(nums)。

因此，P = (target + sum(nums)) / 2。

問題變成了：從 nums 中選出一些數字，使它們的總和恰好等於 P。這是一個0-1 背包問題。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function findTargetSumWays($nums, $target) {
        $sum = array_sum($nums);
        if ($sum < $target || ($sum + $target) % 2 !== 0) {
            return 0;
        }
        
        $p = ($sum + $target) / 2;
        
        $dp = array_fill(0, $p + 1, 0);
        $dp[0] = 1;

        foreach ($nums as $num) {
            for ($i = $num; $i <= $p; $i++) {
                $dp[$i] += $dp[$i - $num];
            }
        }
        return $dp[$p];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯和實現都是正確的。它巧妙地將問題轉換為一個子集和問題，並用動態規劃解決。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。它正確地處理了轉換後的子集和問題。內層迴圈從前往後是因為這是排列數，但這裡其實是組合數。然而，由於每個數字只能用一次（每個數字只能選擇 + 或 -），所以這是一個0-1 背包。

正確的 PHP 解決方案 (Corrected PHP Solution)：

這段程式碼本身就是正確的。我們可以稍微優化內層迴圈，讓它更符合 0-1 背包的標準寫法。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function findTargetSumWays($nums, $target) {
        $sum = array_sum($nums);
        if ($sum < $target || ($sum + $target) % 2 !== 0) {
            return 0;
        }
        
        $positiveSum = ($sum + $target) / 2;
        
        $dp = array_fill(0, $positiveSum + 1, 0);
        $dp[0] = 1;
        
        foreach ($nums as $num) {
            for ($i = $positiveSum; $i >= $num; $i--) {
                $dp[$i] += $dp[$i - $num];
            }
        }
        
        return $dp[$positiveSum];
    }
}

除錯本類問題的技巧：

  1. 數學轉換：當問題的表達式看起來複雜時，嘗試用代數方法簡化它，將其轉換為已知的 DP 模式。

  2. 0-1 背包：再次確認每個物品的使用次數，以選擇正確的迴圈方向。

0516. 最長回文子序列 (Longest Palindromic Subsequence)

問題描述：給定一個字串 s，找到其中最長的回文子序列，並返回該序列的長度。

正確解題思路概述：

這是一個區間動態規劃問題。定義 dp[i][j] 為子字串 s[i...j] 的最長回文子序列長度。

  • 狀態轉移方程：

    • 如果 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2。

    • 如果 s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function longestPalindromeSubseq($s) {
        $n = strlen($s);
        $dp = array_fill(0, $n, array_fill(0, $n, 0));

        for ($i = 0; $i < $n; $i++) {
            $dp[$i][$i] = 1;
        }

        for ($len = 2; $len <= $n; $len++) {
            for ($i = 0; $i <= $n - $len; $i++) {
                $j = $i + $len - 1;
                if ($s[$i] === $s[$j]) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] + 2;
                } else {
                    $dp[$i][$j] = max($dp[$i + 1][$j], $dp[$i][$j - 1]);
                }
            }
        }
        return $dp[0][$n - 1];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的。它精確地實現了區間 DP 的思想。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。它的結構是標準的區間 DP 寫法，先遍歷長度，再遍歷起點，以確保在計算 dp[i][j] 時，dp[i+1][j-1]、dp[i+1][j] 和 dp[i][j-1] 這些子問題的解都已經被計算出來。

正確的 PHP 解決方案 (Corrected PHP Solution)：

由於原程式碼正確，我們只會稍微調整格式以符合風格。

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function longestPalindromeSubseq($s) {
        $n = strlen($s);
        if ($n === 0) {
            return 0;
        }
        
        $dp = array_fill(0, $n, array_fill(0, $n, 0));

        for ($i = $n - 1; $i >= 0; $i--) {
            $dp[$i][$i] = 1;
            for ($j = $i + 1; $j < $n; $j++) {
                if ($s[$i] === $s[$j]) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] + 2;
                } else {
                    $dp[$i][$j] = max($dp[$i + 1][$j], $dp[$i][$j - 1]);
                }
            }
        }
        return $dp[0][$n - 1];
    }
}

除錯本類問題的技巧：

  1. 區間 DP：對於區間 DP，通常遍歷長度或從後往前遍歷 i 來確保子問題被先解決。

  2. 基線情況：明確定義單個字元的子序列長度 (dp[i][i] = 1)。

0518. 零錢兌換 II (Coin Change II)

問題描述：給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函式來計算可以湊成總金額的硬幣組合數。每種硬幣有無限個。

正確解題思路概述：

這是一個完全背包問題。定義 dp[i] 為湊成總金額 i 的組合數。

  • 狀態轉移方程：dp[i] = sum(dp[i - coin])，其中 coin 在 coins 中。

    這個問題是組合數，所以內層迴圈應該是 amount。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer $amount
     * @param Integer[] $coins
     * @return Integer
     */
    function change($amount, $coins) {
        $dp = array_fill(0, $amount + 1, 0);
        $dp[0] = 1;
        
        for ($i = 1; $i <= $amount; $i++) {
            foreach ($coins as $coin) {
                if ($i >= $coin) {
                    $dp[$i] += $dp[$i - $coin];
                }
            }
        }
        return $dp[$amount];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，它計算的是排列數，而不是組合數。

  • 錯誤點：與 0377 題類似，外層迴圈是 amount，內層是 coins。這種寫法會將 (1, 2) 和 (2, 1) 視為不同的組合，這與題目要求「組合數」相違背。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將迴圈順序交換，先遍歷硬幣，再遍歷金額。

PHP
class Solution {
    /**
     * @param Integer $amount
     * @param Integer[] $coins
     * @return Integer
     */
    function change($amount, $coins) {
        $dp = array_fill(0, $amount + 1, 0);
        $dp[0] = 1;
        
        foreach ($coins as $coin) {
            for ($i = $coin; $i <= $amount; $i++) {
                $dp[$i] += $dp[$i - $coin];
            }
        }
        return $dp[$amount];
    }
}

除錯本類問題的技巧：

  1. 排列 vs. 組合：對於背包問題，仔細區分是要求排列數還是組合數。

    • 排列數：先遍歷背包容量，再遍歷物品。

    • 組合數：先遍歷物品，再遍歷背包容量。

0583. 兩個字串的刪除操作 (Delete Operation for Two Strings)

問題描述：給定兩個單詞 word1 和 word2，返回使得 word1 和 word2 相同所需的最少步數。每一步你可以在任一字串上刪除一個字元。

正確解題思路概述：

這是一個與最長公共子序列問題密切相關的動態規劃問題。為了讓兩個字串相等，我們需要刪除掉那些不屬於它們的最長公共子序列的字元。

  • 解法一：先找出 word1 和 word2 的最長公共子序列（Longest Common Subsequence, LCS）的長度 L。然後，最少刪除步數為 (len(word1) - L) + (len(word2) - L)。

  • 解法二：直接使用動態規劃。定義 dp[i][j] 為使得 word1 的前 i 個字元和 word2 的前 j 個字元相等所需的最少刪除步數。

    • 狀態轉移方程：

      • 如果 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]。

      • 如果 word1[i-1] != word2[j-1]：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $word1
     * @param String $word2
     * @return Integer
     */
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        for ($i = 0; $i <= $m; $i++) {
            $dp[$i][0] = $i;
        }
        for ($j = 0; $j <= $n; $j++) {
            $dp[0][$j] = $j;
        }
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($word1[$i - 1] === $word2[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                } else {
                    $dp[$i][$j] = min($dp[$i - 1][$j], $dp[$i][$j - 1]) + 1;
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼是正確的。它完全實現了解法二的動態規劃思路，並且沒有邏輯錯誤。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。它正確地處理了邊界情況（dp[i][0] = i 和 dp[0][j] = j），並正確地應用了狀態轉移方程。這是一個有效的解決方案。

正確的 PHP 解決方案 (Corrected PHP Solution)：

由於原程式碼正確，我們不需要修正。

PHP
class Solution {
    /**
     * @param String $word1
     * @param String $word2
     * @return Integer
     */
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        for ($i = 0; $i <= $m; $i++) {
            $dp[$i][0] = $i;
        }
        for ($j = 0; $j <= $n; $j++) {
            $dp[0][$j] = $j;
        }
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($word1[$i - 1] === $word2[$j - 1]) {
                    $dp[$i][j] = $dp[$i - 1][$j - 1];
                } else {
                    $dp[$i][j] = min($dp[$i - 1][$j], $dp[$i][$j - 1]) + 1;
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯本類問題的技巧：

  1. 問題轉換：將一個看起來像是字串編輯距離或匹配的問題，轉換為最長公共子序列（LCS）或其變種。

  2. 狀態定義：清晰地定義 dp[i][j] 的含義，這有助於推導正確的狀態轉移方程。

0647. 回文子串 (Palindromic Substrings)

問題描述：給定一個字串 s，計算 s 中有多少個回文子串。

正確解題思路概述：

這是一個動態規劃問題。定義 dp[i][j] 為子字串 s[i...j] 是否為回文。

  • 狀態轉移方程：

    • 如果 s[i] == s[j] 且子字串 s[i+1...j-1] 是回文，則 s[i...j] 也是回文。

    • dp[i][j] = (s[i] == s[j]) && (j - i <= 1 || dp[i+1][j-1])。

  • 迴圈順序：為了確保在計算 dp[i][j] 時，dp[i+1][j-1] 已經被計算，我們需要從後往前遍歷 i，或從前往後遍歷長度 len。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function countSubstrings($s) {
        $n = strlen($s);
        if ($n === 0) {
            return 0;
        }

        $count = 0;
        $dp = array_fill(0, $n, array_fill(0, $n, false));

        for ($i = 0; $i < $n; $i++) {
            $dp[$i][$i] = true;
            $count++;
        }

        for ($i = 0; $i < $n - 1; $i++) {
            if ($s[$i] === $s[$i + 1]) {
                $dp[$i][$i + 1] = true;
                $count++;
            }
        }

        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 2; $j < $n; $j++) {
                if ($s[$i] === $s[$j] && $dp[$i + 1][$j - 1]) {
                    $dp[$i][$j] = true;
                    $count++;
                }
            }
        }
        return $count;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，其迴圈順序不正確。

  • 錯誤點：外層迴圈 for ($i = 0; i < $n; $i++) 和內層迴圈 for ($j = $i + 2; $j < $n; $j++) 的順序導致了問題。在計算 dp[i][j] 時，$dp[$i + 1][$j - 1] 可能還沒有被計算，因為 j-1 可能小於 j，但 i+1 可能大於 i。這打破了 DP 的依賴關係。例如，當 s = "aba" 時，i=0, j=2 時，$dp[1][1] 已經計算；但當 s = "abacaba" 時，i=0, j=6 時，需要 dp[1][5]，但 dp[1][5] 還沒有計算。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用正確的迴圈順序，先遍歷長度或從後往前遍歷。

PHP
class Solution {
    /**
     * @param String $s
     * @return Integer
     */
    function countSubstrings($s) {
        $n = strlen($s);
        if ($n === 0) {
            return 0;
        }
        
        $count = 0;
        $dp = array_fill(0, $n, array_fill(0, $n, false));

        for ($i = $n - 1; $i >= 0; $i--) {
            for ($j = $i; $j < $n; $j++) {
                if ($s[$i] === $s[$j]) {
                    if ($j - $i <= 1 || $dp[$i + 1][$j - 1]) {
                        $dp[$i][$j] = true;
                        $count++;
                    }
                }
            }
        }
        return $count;
    }
}

除錯本類問題的技巧：

  1. 迴圈順序：對於區間 DP，確保子問題（較小的區間）先被計算。通常是先遍歷長度，再遍歷起點，或者從後往前遍歷起點。

  2. 基線情況：單個字元和兩個相鄰相同字元的子串是回文的基線情況，需要正確處理。

0673. 最長遞增子序列的個數 (Number of Longest Increasing Subsequence)

問題描述：給定一個未排序的整數陣列 nums，返回最長遞增子序列的個數。

正確解題思路概述：

這是一個在最長遞增子序列問題基礎上的延伸。我們需要兩個 DP 陣列：

  • dp[i]：以 nums[i] 結尾的最長遞增子序列的長度。

  • count[i]：以 nums[i] 結尾的最長遞增子序列的個數。

  • 狀態轉移方程：

    • dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]。

    • count[i]：當 dp[j] + 1 等於新的 dp[i] 時，count[i] += count[j]。如果 dp[j] + 1 等於舊的 dp[i]，則 count[i] += count[j]。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findNumberOfLIS($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return $n;
        }

        $dp = array_fill(0, $n, 1);
        $count = array_fill(0, $n, 1);
        $maxLen = 1;

        for ($i = 1; $i < $n; $i++) {
            for ($j = 0; $j < $i; $j++) {
                if ($nums[$i] > $nums[$j]) {
                    if ($dp[$j] + 1 > $dp[$i]) {
                        $dp[$i] = $dp[$j] + 1;
                        $count[$i] = $count[$j];
                    } else if ($dp[$j] + 1 === $dp[$i]) {
                        $count[$i] += $count[$j];
                    }
                }
            }
            $maxLen = max($maxLen, $dp[$i]);
        }
        
        $result = 0;
        for ($i = 0; $i < $n; $i++) {
            if ($dp[$i] === $maxLen) {
                $result += $count[$i];
            }
        }
        return $result;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的。它完全實現了雙 DP 陣列的解法。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。它正確地處理了兩種情況：當發現一個更長的子序列時，更新長度和個數；當發現一個等長的子序列時，只累加個數。

正確的 PHP 解決方案 (Corrected PHP Solution)：

由於原程式碼正確，我們不需要修正。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findNumberOfLIS($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return $n;
        }

        $dp = array_fill(0, $n, 1);
        $count = array_fill(0, $n, 1);
        $maxLen = 1;

        for ($i = 1; $i < $n; $i++) {
            for ($j = 0; $j < $i; $j++) {
                if ($nums[$i] > $nums[$j]) {
                    if ($dp[$j] + 1 > $dp[$i]) {
                        $dp[$i] = $dp[$j] + 1;
                        $count[$i] = $count[$j];
                    } else if ($dp[$j] + 1 === $dp[$i]) {
                        $count[$i] += $count[$j];
                    }
                }
            }
            $maxLen = max($maxLen, $dp[$i]);
        }
        
        $result = 0;
        for ($i = 0; $i < $n; $i++) {
            if ($dp[$i] === $maxLen) {
                $result += $count[$i];
            }
        }
        return $result;
    }
}

除錯本類問題的技巧：

  1. 雙 DP 陣列：當問題需要額外資訊（如數量）時，考慮使用額外的 DP 陣列來儲存。

  2. 狀態更新：仔細思考狀態轉移時，如何更新輔助 DP 陣列的值。

0674. 最長連續遞增序列 (Longest Continuous Increasing Subsequence)

問題描述：給定一個未排序的整數陣列 nums，返回最長連續遞增序列的長度。

正確解題思路概述：

這是一個非常簡單的動態規劃問題。定義 dp[i] 為以 nums[i] 結尾的最長連續遞增序列的長度。

  • 狀態轉移方程：

    • 如果 nums[i] > nums[i-1]：dp[i] = dp[i-1] + 1。

    • 否則：dp[i] = 1。

  • 這個問題也可以用貪心演算法，用一個 count 變數來追蹤當前長度，然後在每次更新 max。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findLengthOfLCIS($nums) {
        $n = count($nums);
        if ($n <= 1) {
            return $n;
        }

        $dp = array_fill(0, $n, 1);
        $maxLength = 1;

        for ($i = 1; $i < $n; $i++) {
            if ($nums[$i] > $nums[$i - 1]) {
                $dp[$i] = $dp[$i - 1] + 1;
            }
            $maxLength = max($maxLength, $dp[$i]);
        }
        return $maxLength;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的。它完全實現了動態規劃的解法。

  • 錯誤點：這段程式碼沒有明顯的邏輯錯誤。它正確地處理了兩種情況，並追蹤了最大長度。它是一個有效的解決方案。

正確的 PHP 解決方案 (Corrected PHP Solution)：

由於原程式碼正確，我們不需要修正。

PHP
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findLengthOfLCIS($nums) {
        $n = count($nums);
        if ($n === 0) {
            return 0;
        }
        
        $count = 1;
        $maxLength = 1;
        
        for ($i = 1; $i < $n; $i++) {
            if ($nums[$i] > $nums[$i - 1]) {
                $count++;
            } else {
                $count = 1;
            }
            $maxLength = max($maxLength, $count);
        }
        return $maxLength;
    }
}

除錯本類問題的技巧：

  1. 簡單 DP：對於只需要依賴於前一個狀態的 DP，考慮用幾個變數來代替整個 DP 陣列，以實現空間優化。

  2. 貪心法：對於這種連續子序列問題，貪心演算法通常是更簡單、更有效的解法。

0714. 買賣股票的最佳時機含手續費 (Best Time to Buy and Sell Stock with Transaction Fee)

問題描述：最多可以完成無限次交易，但每次交易要支付固定的手續費。求能獲得的最大利潤。

正確解題思路概述：

這是一個帶有額外狀態的動態規劃問題，與含冷凍期的問題類似。

  • 狀態定義：

    • hold：在當天結束時，手頭持有股票的最大利潤。

    • cash：在當天結束時，手頭沒有股票的最大利潤。

  • 狀態轉移方程：

    • hold = max(hold, cash - price) （買入或維持）

    • cash = max(cash, hold + price - fee) （賣出或維持）

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @param Integer $fee
     * @return Integer
     */
    function maxProfit($prices, $fee) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        $hold = -$prices[0] - $fee;
        $cash = 0;
        
        for ($i = 1; $i < $n; $i++) {
            $prevHold = $hold;
            $hold = max($hold, $cash - $prices[$i]);
            $cash = max($cash, $prevHold + $prices[$i] - $fee);
        }
        
        return $cash;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是正確的，但初始化 hold 的方式有點問題。

  • 錯誤點：$hold = -$prices[0] - $fee;。將手續費在買入時扣除是合理的，但更常見的寫法是在賣出時扣除。這段代碼的邏輯是正確的，因為 cash - prices[i] 是一個買入操作，其結果會被用來更新 hold，而手續費在 cash 的來源 (hold + prices[i] - fee) 中已經被扣除。所以這裡沒有邏輯錯誤。這段程式碼實際上是正確的。

正確的 PHP 解決方案 (Corrected PHP Solution)：

由於原程式碼正確，我們不需要修正。

PHP
class Solution {
    /**
     * @param Integer[] $prices
     * @param Integer $fee
     * @return Integer
     */
    function maxProfit($prices, $fee) {
        $n = count($prices);
        if ($n <= 1) {
            return 0;
        }

        $hold = PHP_INT_MIN;
        $cash = 0;

        foreach ($prices as $price) {
            $prevHold = $hold;
            $hold = max($hold, $cash - $price);
            $cash = max($cash, $prevHold + $price - $fee);
        }
        return $cash;
    }
}

除錯本類問題的技巧：

  1. 狀態定義：明確定義 hold 和 cash 兩種狀態，並思考其依賴關係。

  2. 交易費/冷凍期：將額外的成本或約束納入狀態轉移方程。

0718. 最長重複子陣列 (Maximum Length of Repeated Subarray)

問題描述：給定兩個整數陣列 A 和 B，返回兩個陣列中最長公共子陣列的長度。

正確解題思路概述：

這是一個動態規劃問題，與最長公共子序列類似，但要求是連續的子陣列。

  • 狀態定義：dp[i][j] 為以 A[i-1] 和 B[j-1] 結尾的最長公共子陣列的長度。

  • 狀態轉移方程：

    • 如果 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1。

    • 如果 A[i-1] != B[j-1]：dp[i][j] = 0。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function findLength($A, $B) {
        $m = count($A);
        $n = count($B);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        $maxLength = 0;
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($A[$i] === $B[$j]) { // 錯誤點
                    $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                    $maxLength = max($maxLength, $dp[$i][$j]);
                }
            }
        }
        
        return $maxLength;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，索引越界。

  • 錯誤點：$A[$i] === $B[$j] 是錯誤的。DP 陣列的大小是 (m+1) x (n+1)，所以索引應該是 A[$i-1] 和 B[$j-1]。當 $i=m 時，$A[$i] 會導致索引越界。

正確的 PHP 解決方案 (Corrected PHP Solution)：

修正索引錯誤。

PHP
class Solution {
    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function findLength($A, $B) {
        $m = count($A);
        $n = count($B);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        $maxLength = 0;
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($A[$i - 1] === $B[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                    $maxLength = max($maxLength, $dp[$i][$j]);
                }
            }
        }
        
        return $maxLength;
    }
}

除錯本類問題的技巧：

  1. 索引：對於 DP 陣列，特別是 (n+1) 大小的陣列，要特別注意索引的使用。dp[i][j] 通常對應的是原始陣列的 i-1 和 j-1 索引。

  2. 區分序列和子陣列：子序列不要求連續，但子陣列要求連續，這會影響狀態轉移方程的設計。

0746. 使用最小花費爬樓梯 (Min Cost Climbing Stairs)

問題描述：給定一個陣列 cost，cost[i] 是從 i 階樓梯開始爬所需的花費。每步你可以爬 1 階或 2 階。你可以從第 0 階或第 1 階開始。返回到達樓梯頂部的最小花費。

正確解題思路概述：

這是一個簡單的動態規劃問題。定義 dp[i] 為爬到第 i 階樓梯所需的最小花費。

  • 狀態轉移方程：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

  • 最終的答案是 min(dp[n-1] + cost[n-1], dp[n-2] + cost[n-2])，但更優雅的解法是將 DP 陣列大小設為 n+1，其中 dp[n] 代表到達頂部的花費。

    • dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

    • 最終答案是 dp[n]。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost) {
        $n = count($cost);
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $cost[0];
        }

        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 0;
        $dp[1] = 0; // 錯誤點

        for ($i = 2; $i <= $n; $i++) {
            $dp[$i] = min($dp[$i - 1] + $cost[$i - 1], $dp[$i - 2] + $cost[$i - 2]);
        }
        return $dp[$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，dp[1] 的初始化不正確。

  • 錯誤點：$dp[1] = 0;。這表示爬到第一階的花費是 0，這是不對的。爬到第一階的花費應該是 cost[1]。

  • 更根本的錯誤：dp[i] 的定義是「到達第 i 階的最小花費」，那麼 dp[0] 和 dp[1] 的花費應該是 cost[0] 和 cost[1]。但因為你可以從第 0 或第 1 階開始，所以到達第 0 階的花費是 cost[0]，到達第 1 階的花費是 cost[1]。

正確的 PHP 解決方案 (Corrected PHP Solution)：

使用正確的初始值，並將 DP 陣列大小設為 n。

PHP
class Solution {
    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost) {
        $n = count($cost);
        if ($n <= 1) {
            return $cost[0];
        }

        $dp = array_fill(0, $n, 0);
        $dp[0] = $cost[0];
        $dp[1] = $cost[1];

        for ($i = 2; $i < $n; $i++) {
            $dp[$i] = min($dp[$i - 1], $dp[$i - 2]) + $cost[$i];
        }

        return min($dp[$n - 1], $dp[$n - 2]);
    }
}

除錯本類問題的技巧：

  1. 狀態定義：仔細定義 dp[i] 的含義是「到達」還是「從...開始」。

  2. 基線情況：確保初始值設置正確，這通常是 DP 問題中最容易出錯的地方。

1035. 不相交的線 (Uncrossed Lines)

問題描述：給定兩個整數陣列 A 和 B。我們可以在 A 和 B 之間畫線，連接相同的數字。要求這些線不能相交。求可以畫出的不相交的線的最大數量。

正確解題思路概述：

這是一個隱藏的最長公共子序列（LCS）問題。由於連接線不能相交，我們必須將 A 和 B 中的數字按照從左到右的順序進行匹配。這與 LCS 問題的定義完全吻合。

  • 狀態定義：dp[i][j] 為 A 的前 i 個元素和 B 的前 j 個元素的最長公共子序列長度。

  • 狀態轉移方程：

    • 如果 A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1。

    • 如果 A[i-1] != B[j-1]：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function maxUncrossedLines($A, $B) {
        $m = count($A);
        $n = count($B);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($A[$i] === $B[$j]) { // 錯誤點
                    $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                } else {
                    $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，存在索引越界。

  • 錯誤點：$A[$i] === $B[$j] 是錯誤的。DP 陣列的大小是 (m+1) x (n+1)，所以索引應該是 A[$i-1] 和 B[$j-1]。當 $i=m 時，$A[$i] 會導致索引越界。

正確的 PHP 解決方案 (Corrected PHP Solution)：

修正索引錯誤。

PHP
class Solution {
    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function maxUncrossedLines($A, $B) {
        $m = count($A);
        $n = count($B);
        
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($A[$i - 1] === $B[$j - 1]) {
                    $dp[$i][j] = $dp[$i - 1][j - 1] + 1;
                } else {
                    $dp[$i][j] = max($dp[$i - 1][j], $dp[$i][j - 1]);
                }
            }
        }
        
        return $dp[$m][$n];
    }
}

除錯本類問題的技巧：

  1. 抽象思維：將一個看似複雜的幾何問題，抽象為一個簡單的動態規劃問題（LCS）。

  2. 索引：再次強調，DP 陣列的索引和原始陣列的索引是不同的，需要仔細處理。

1049. 最後一塊石頭的重量 II (Last Stone Weight II)

問題描述：有一堆石頭，每塊石頭都有一個正整數重量 stones[i]。每回合，你選擇兩塊石頭 x 和 y，它們的重量分別為 x 和 y。如果 x == y，兩塊石頭都粉碎；如果 x != y，則重量為 x 的石頭被粉碎，重量為 y 的石頭重量變為 y - x。求最後剩下石頭的最小可能重量。

正確解題思路概述：

這是一個轉換為0-1 背包問題的動態規劃。

  • 將所有石頭分成兩堆，一堆總重為 sum1，另一堆總重為 sum2。最後剩下的重量是 |sum1 - sum2|。

  • 為了使 |sum1 - sum2| 最小，我們應該讓 sum1 和 sum2 盡可能接近。

  • 設所有石頭的總重為 sum，則 sum1 + sum2 = sum，所以 sum2 = sum - sum1。最後重量為 |sum1 - (sum - sum1)| = |2*sum1 - sum|。

  • 為了使這個值最小，我們需要讓 sum1 盡可能接近 sum / 2。

  • 問題轉化為：從 stones 中選出一些石頭，使它們的總重最接近 sum / 2。這是一個 0-1 背包問題：背包容量為 sum / 2，物品重量和價值都是 stones[i]。

帶有錯誤的程式碼 (Buggy Solution)：

PHP
class Solution {
    /**
     * @param Integer[] $stones
     * @return Integer
     */
    function lastStoneWeightII($stones) {
        $sum = array_sum($stones);
        $target = floor($sum / 2);
        
        $dp = array_fill(0, $target + 1, false);
        $dp[0] = true;
        
        foreach ($stones as $stone) {
            for ($i = $stone; $i <= $target; $i++) { // 錯誤點
                $dp[$i] = $dp[$i] || $dp[$i - $stone];
            }
        }
        
        $maxSum1 = 0;
        for ($i = $target; $i >= 0; $i--) {
            if ($dp[$i]) {
                $maxSum1 = $i;
                break;
            }
        }
        
        return $sum - 2 * $maxSum1;
    }
}

除錯分析 (Debugging Analysis)：

這段程式碼的邏輯是錯誤的，它實現的是完全背包。

  • 錯誤點：for ($i = $stone; $i <= $target; $i++)。內層迴圈從前往後遍歷。這會導致同一個石頭被重複使用，而每塊石頭只能用一次。

正確的 PHP 解決方案 (Corrected PHP Solution)：

將內層迴圈的方向改為從後往前遍歷。

PHP
class Solution {
    /**
     * @param Integer[] $stones
     * @return Integer
     */
    function lastStoneWeightII($stones) {
        $sum = array_sum($stones);
        $target = floor($sum / 2);
        
        $dp = array_fill(0, $target + 1, false);
        $dp[0] = true;
        
        foreach ($stones as $stone) {
            for ($i = $target; $i >= $stone; $i--) {
                $dp[$i] = $dp[$i] || $dp[$i - $stone];
            }
        }
        
        $maxSum1 = 0;
        for ($i = $target; $i >= 0; $i--) {
            if ($dp[$i]) {
                $maxSum1 = $i;
                break;
            }
        }
        
        return $sum - 2 * $maxSum1;
    }
}

除錯本類問題的技巧：

  1. 問題轉換：將一個抽象的「粉碎石頭」問題，轉換為一個具體的背包問題。

  2. 0-1 背包：再次確認每個物品的使用次數，以選擇正確的迴圈方向。

於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)

熱門文章

  • 資深前端工程師面試指南：Nuxt 3 生命週期與 SSR、CSR、SSG 渲染策略
      資深前端工程師面試指南：Nuxt 3 生命週期與 SSR、CSR、SSG 渲染策略 在資深前端工程師的面試中，Nuxt 3 是一個熱門話題，尤其是其生命週期以及伺服器端渲染 (SSR)、客戶端渲染 (CSR) 和靜態生成 (SSG) 的應用場景。這些議題不僅考驗對框架的理解...
  • 資料庫設計與優化題庫（適用 MySQL / Laravel）
      資料庫設計與優化題庫（適用 MySQL / Laravel） 在現代 Web 應用開發中，資料庫設計與優化是資深後端工程師的核心技能，尤其在使用 MySQL 與 Laravel 框架時。本文將提供的題庫擴展為一篇技術文章，分為四大類別。每個問題不僅列出，還附上深入解析、程式...
  • 🧠 Vue3 + Nuxt3 面試速答小抄（完整版）
      🧠 Vue3 + Nuxt3 面試速答小抄（完整版） 這份速答小抄專為準備 Vue3 與 Nuxt3 面試的開發者設計，採用「方法論 → 案例 → 專業詞彙 → 結果/影響」結構，幫助你在 30 秒內精準展現專業深度，並針對 async 相關問題補充細節。每題都可濃縮為...
  • 資深前端工程師面試指南：Vue 與 Nuxt 篇
      資深前端工程師面試指南：Vue 與 Nuxt 篇 資深前端工程師的面試不僅考驗 Vue 和 Nuxt 的基本語法，還深入探討架構設計、效能優化、SSR、SEO、安全性、測試與團隊協作等層面。本文將提供的問題列表擴展為一篇技術文章，分為六大類別。每個問題附上深入解析、程式碼範...
  • 🧩 PHP/Laravel 工程師十大常見面試問題速答小抄
      🧩 PHP/Laravel 資深工程師十大常見面試問題速答小抄（詳細版含演算法與底層原理） 以下是針對 PHP/Laravel 資深工程師面試的十大常見問題，答案經過優化，融入底層原理（如 CORS）、詳細技術細節、具體案例、量化成果與演算法問題，幫助你在面試中展現專業深...
  • 🧭 AI Debug & 開發提示詞範本庫（Laravel 專用）
    🧭 AI Debug & 開發提示詞範本庫（Laravel 專用） 這份範本庫提供一系列標準化的提示詞，幫助 PHP/Laravel 開發者在 Debug、功能開發與進階應用中高效利用 AI 作為程式副駕駛。範本適用於 Laravel 10/11 與 PHP 8.x 環...
  • 資深 PHP 後端面試追問應答手冊
      資深 PHP 後端面試追問應答手冊 這份手冊整理了資深 PHP 後端工程師面試中常見的追問問題與結構化回答，涵蓋 Debug、架構設計、效能優化、安全性、團隊合作與 DevOps 等面向。每個回答遵循 方法論 → 案例 → 專業詞彙 → 結果/影響 的公式，幫助你在面試中...
  • 🚀 AI 提示詞最佳實踐：Vue3 / Nuxt3 開發與除錯指南
    🚀 AI 提示詞最佳實踐：Vue3 / Nuxt3 開發與除錯指南 在現代前端開發中，AI 已成為提高效率的強大工具。然而，如何精準地向 AI 提問，是釋放其潛能的關鍵。這份指南將提供一系列針對 Vue3 和 Nuxt3 的提示詞範本，涵蓋從基礎除錯到進階功能開發，幫助你更...
  • 資深 PHP 後端面試追問應答手冊 - Redis 應用篇
      資深 PHP 後端面試追問應答手冊 - Redis 應用篇 本篇為 「資深 PHP 後端面試追問應答手冊」 的補充，聚焦於 Redis 在 PHP（特別是 Laravel）中的進階應用。Redis 作為高效的記憶體資料庫，在快取、隊列、即時通信、會話管理和分散式鎖等場景...
  • 非技術面試速答小抄：以 STAR 法則展現職場成熟度
      非技術面試速答小抄：以 STAR 法則展現職場成熟度 在技術面試中，除了程式設計和系統設計題目外， 行為面試問題 同樣至關重要。這些問題能展現你的軟性技能、解決問題的能力以及團隊合作力。本小抄提供以 STAR 法則（情境 Situation → 任務 Task → 行動 A...