算法进击

1. 困惑

我经常看到一个算法题，medium类型的，就蒙圈了。
或者有一个暴力破解的想法，然后不能用暴力破解，又不知道怎么办了。
感觉算法题的解题思路是，首先一个题目，一定有目的，这个目的一般是一个答案，要么是一个值，要么是一个列表，要么是一次排序。
一个值 有很多含义，最大(小)值，是否存在，总数等等
不同的目的，有不同的类型算法去解决，可能一个问题有很多类型算法都能解决，这时候又涉及到最优解的问题。
最优解往往是一个公式，得出公式，实现上需要考虑边界问题，才能设计出好的实现

2. 该怎么学习

将算法解题拆分成 解法 和 结构

同一类问题下都是同一类解法，只是在不同的结构下有不同的实现方式，不同的结构的实现的效率往往又不相同

因此，怎么学习比较好呢？

1. 先掌握好共有多少类型的问题（这个不现实）
2. 掌握不同解法，这些解法，针对的类型有哪些
3. 掌握不同数据结构，往往怎么实现对应的解法

4. （最优化原理）动态规划 DP(dynamic programming)

原理

• 最优子结构性质
• 子问题重叠性质
• 无后效性，以前各阶段的状态无法直接影响它未来的决策

基本概念

1. 阶段(分阶段进行, k表示在第几阶段)
2. 状态(第k阶段的状态，可以用数组x[k], k=1,2,3)
3. 决策(本阶段某状态出发堆下一阶段状态所作出的选择，决策变量 u[k](x[k]))
4. 状态转移方程(x[k+1] = T(x[k], u[k]))

例2（带回收的资源分配问题）某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所代替。此机床如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得的利润最大？
动态规划知识点

过程和结果

1. 逆着阶段的顺序进行
2. 可以得出最优策略和最优目标，已经所有过程最优状态

• 将问题按时间或空间次序划分成若干阶段
• 正确选择状态变量。这一步是形成动态模型的关键，状态变量是动态规划模型中最重要的参数。一般来说，状态变量应具有以下三个特性：
  1. 要能够用来描述决策过程的演变特征。
  2. 要满足无后效性。即如果某阶段状态已给定后，则以后过程的进展不受以前各状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的发展。
  3. 递推性。即由k阶段的状态变量及决策变量uk可以计算出k+1阶段的状态变量。
• 确定决策变量及允许决策变量集合Dk()。
• 根据状态变量之间的递推关系，写出状态转移方程：
• 建立指标函数

• 建立动态规划方程：
  动态规划方程.png
  
  
  动态规划方程.png
  
  

  一般会规定一个范围f(n)，超过范围的都为0->f(n+1)=0

  
  
  推倒过程.png

简单DP

主要包括递推、背包、LIS（最长递增序列），LCS（最长公共子序列）

区间DP

区间dp,一般是枚举区间，把区间分成左右两部分，然后求出左右区间再合并

树形DP

树形dp是建立在树这种数据结构上的dp，一般状态比较好想，通过dfs维护从根到叶子或从叶子到根的状态转移

数位DP

数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数，它是按位来进行计数统计的，可以保存子状态，速度较快。数位dp做多了后，套路基本上都差不多，关键把要保存的状态给抽象出来，保存下来。

概率（期望）DP

一般来说概率正着推，期望逆着推。有环的一般要用到高斯消元解方程。期望可以分解成多个子期望的加权和，权为子期望发生的概率，即 E(aA+bB+...) = aE(A) + bE(B) +...

数据结构优化 DP

有时尽管状态找好了，转移方程的想好了，但时间复杂度比较大，需要用数据结构进行优化。常见的优化有二进制优化、单调队列优化、斜率优化、四边形不等式优化等。