Dynamic Programming Anonymous published on 2023-12-26 included in Algorithm定义状态转移方程的关键在于对状态做出完整表示,举个例子,最长上升子序列问题中,不同的状态是一些子序列,以子序列的最后一项作为划分依据就可以完整表示不同的状态
Greedy Algorithm Anonymous published on 2023-12-24 included in Algorithm贪心策略正确性证明 归纳法 归纳法证明的核心逻辑:证明采用贪心策略执行到任意步数时获得的解都是最优解的一部分
Divide and Conquer Algorithm Anonymous published on 2023-12-22 included in Algorithm4 种递归式求解方法 代入法 猜测一个界,然后用数学归纳法证明这个界是正确的。
Programming Complexity Anonymous published on 2023-12-22 included in Algorithm渐进符号及相应定理 $O$$f(n)=O(g(n))$ 称 g(n)是 f(n)的一个渐近上界
Approximation Algorithm Anonymous published on 2023-12-22 included in Algorithm基本概念 近似比近似算法产生解的代价:C, 最优解产生解的代价:$C^*$