动态规划
计数
有多少种方式走到右下角
有多少种方法选出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) 的
字典树