动态规划
计数
有多少种方式走到右下角
有多少种方法选出k个数使得和是sum
求最大最小值
从左上角走到右下角路径的最大数字和
最长上升子序列长度
求存在性
取石子游戏，先手是否必胜
能不能选出k个数使得和是sum
组成部分：
- 确定状态，类似数学的未知数，开一个数组，1）最后一步；2）子问题
换硬币：
递归（做了很多重复计算，效率低下）：
int f(int x){
if (x==0) return 0;
int res = MAX_VALUE;
if (x≥2) res=math.min(f(x-2)+1, res）
if(x≥5) res = math.min(f(x-5)+1, res)
if(x≥7) res = math.min(f(x-7)+1, res)
return res
}
2. 转移方程：根据子问题定义直接得到
f(x) = min{f(x–2)+1, f(x–5)+1, f(x–7)+1}
3. 初始条件和边界情况
x-2, x-5,x-7小于0怎么办？什么时候停下来？
如果不能拼出y，就定义f[y]=正无穷，例如f[-1]=f[-2]=…=正无穷
所以 f[1]=min{f[-1]+1,f[-4]+1,f[-6]+1}=正无穷，表示拼不出来1
初始条件：f[0]=0
4.计算顺序：每一步尝试三种硬币，一共27步，与递归算法相比，没有任何重复计算，算法时间复杂度（即需要进行的步数）：27（数的大小）*3（硬币数）
并查集
缺点：没有用路径压缩，不是 O(1)
路径压缩的时间复杂度 O(1)
并查集的所有操作都是 O(1) 的
字典树
