算法设计
July 4, 2022
算法设计的常用方法 # 双指针 # 滑动窗口 # 动态规划 # 二分法 # 贪心 #
algo-design
分治
June 3, 2022
定义 # 分治：将 大问题 拆为 不相交 的 规模更小 的 子问题 ， 根据子问题的解求出原始问题的解 分：大问题拆为小问题 治：解决小问题 合：由小问题的解合为大问题的解 分治的复杂度分析 # Substitution method # 替换法 Recursion-tree method # 递归树方法 Master method # 主定理
动态编程
June 3, 2022
Dynamic Programming # 动态规划: 由子问题的解推出最终问题的解，子问题重叠，即子问题共享子子问题 避免重复计算子问题 通常用于解决最优问题（最小，最大），求最优解 动态规划的基本元素 # Optimal Substructure # 最优子结构，通过子问题的最优解，求出最终的最优解 Overlapping Subproblem # 重叠子问题
贪心算法
June 3, 2022
草稿，待完善 Greedy # 贪心 每一步都求最优解
切钢条问题
June 3, 2022
Rod-Cutting # 切钢条问题 钢条长度 i 和售价 P(i) 的对照表 Length i 1 2 3 4 5 6 7 8 9 10 Price P(i) 1 5 8 9 10 17 17 20 24 30 Cut ways 1 2 4 8 求给定长度 n 的钢条的最大销售额 R(n) ? 解： 设长度为 n 的钢条的最大销售额为 R(n) R(n) = Max {P(n), R(1) + R(n -1), R(2) + R(n - 2)}