Algorithm

可以跟着 Carl 刷, 地址 。

个人认为算法最难的有：

• 回溯
• 贪心
• 动态规划

回溯

一般可以解决如下几种问题：

• 组合问题： 在N个数里面按照规则找出K个数的集合
• 切割问题： 一个字符串按照规则有几种切割方式
• 子集问题： N个数的集合里有多少符合条件的子集
• 排列问题： N个数按一定规则全排列，有几种排列方式
• 棋盘问题： N皇后，数独等

解题有固定模板，按照模板往下写。

贪心

贪心的本质是选择每一个阶段的局部最优，从而达到全局最优。 贪心算法没有固定套路模板，最好的策略就是举反例，如果想不到，就试一试贪心。 解决问题就是常识性推导加上举反例。

一般解题的4个步骤：

1. 将问题分解成若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

动态规划

Dynamic Programming，简称 DP 。如果某一问题有很多重叠子问题，使用动态规划是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心，贪心没有状态推导，而是从局部直接选出最优的。

解决的问题：

1. 常见的基础问题，如斐波那契数，爬楼梯，不同路径等
2. 背包问题
3. 打家劫舍
4. 股票问题
5. 子序列问题