dynamic-programming

動態規劃 (DP) 技能模組專為軟體工程師、學生及競賽程式設計者打造，旨在解決複雜的最優化問題。本技能提供一套紮實的開發框架，引導使用者將遞迴問題轉化為高效的迭代解決方案。透過專注於狀態定義、遞迴關係、邊界條件、計算順序及空間複雜度優化，本技能協助使用者將指數時間複雜度的暴力解法轉換為 O(n) 或 O(n*W) 的高效演算法。無論是在技術面試準備、生產環境演算法優化，或是開發需要高效率資源管理的軟體元件，本技能均能發揮關鍵作用。使用者可藉此處理典型的動態規劃範式，包含費氏數列變體、0/1 背包問題、最長共同子序列 (LCS)、零錢兌換及最長遞增子序列 (LIS)。

• 提供包含使用 functools.lru_cache 的由上而下備忘錄實作，以及由下而上的表格化迭代策略。

• 內建進階空間優化技術，在適用情況下將記憶體開銷從 O(n) 降至 O(1)。

• 提供用於背包問題、序列比對與組合優化的模組化程式碼模式，確保高度的程式碼複用性。

• 具備嚴格的參數驗證機制，並針對遞迴深度與記憶體限制提供穩健的錯誤處理。

• 符合 SASMP v1.3.0 協議規範，可無縫整合至資料結構演算法助手代理框架中。

• 輸入需求：預期接收序列清單、整數目標值，以及選用的備忘錄字典，以確保函數呼叫的彈性。

• 適用情境：最適合用於具有重疊子問題 (overlapping subproblems) 與最佳子結構 (optimal substructure) 特性的演算法難題。

• 使用建議：當遞迴深度成為效能瓶頸時，建議優先採用迭代表格化方法，以避免呼叫堆疊溢位。

• 整合性：可透過 Claude Code 的斜線指令直接調用，自動生成程式碼模板並對既有演算法進行最佳化。