枚举

• 背景
  • 找不到合适的数学公式和技巧
  • （改良后）枚举复杂度不是特别大
  • 通常用于找到一种情况使之满足题意的题目
  • 配合假设法找到目标情形：假币问题
• 技巧
  • 跳跃枚举法：跳过对没有必要的情况的枚举
  • 局部枚举法：枚举局部，剩下的由该局部确定。例如熄灯问题

# 递归

• 作用
  • 替代多重循环，如：n皇后问题。
    • 这种类型往往要运用到一个==全局/静态变量==来存储前面算过的结果，譬如n皇后就用到了一个全局数组来保存每一行的皇后拜访情况。全局/静态变量的好处就在于==所有递归函数共享成果==，就像==递推迭代==一样，每一步会影响下一步。
    • 递归函数形式：T function( T f(n) )，函数意义：在前n-1步已经完成的情况下决定如何走第n步，往往第一个被调用的function参数为0或1（然后依次调用1~n0）
  • 解决实质是递归形式的问题
    • 有些问题本身就是==递归定义==的，比如不少表达式就是递归定义的：逆波兰，四则运算。逆波兰==直接递归==调用自身定义，四则运算则包含项，因子和表达式自身等多个概念，是一种==间接递归==调用自身定义
    • 函数，数列的递推公式
    • 关键是搞清楚问题是怎样递归定义的，可以借助画图，写代数式的办法捋清楚。
  • 将问题分解为规模更小的子问题来求解
    • 如何来分解？
    • ==“n=1+(n-1)”法==
      • 比方说要解决一个规模为n的问题，先找到解决该问题的==第一步==怎么做，然后再把剩下的问题解决，剩下的问题规模刚好是n-1且解决过程自相似，可以用上递归n-1。e.g.台阶问题
    • ==“n=(n-1)+1”法==
      • 先解决n-1问题，再将最后一步完善,e.g.汉诺塔问题
    • 与多重循环不同，该方法第一个调用的function参数往往时n0总规模
    • 与分治不同，分治往往偏向于均分，而且多了一步综合，不过分治与递归又可以相互补充

附注

1. atof（）函数，将浮点串转变为浮点数
2. cin.peek（）函数，提前预知输入而非读取
3. 浮点数的比较引入eps

分治

• 基本思想
  • 将一个问题拆分成两个或两个以上规模更小的问题，然后将小问题分别解决或只解决==部分==问题，最后==综合处理==一次。
• 一般模式：分划，局部处理，综合处理（分治 | 归并）
  • 常常与==递归==思想结合
• 作用：使==规模缩小==，提高算法效率（想想：不断地递归并分治，使得规模不断二分）
• 应用举例：基于分治策略的快速排序和归并排序

附注

1. " x & 1 " 表达式判别x奇偶性
2. 快速幂算法

动态规划

• 背景
  • 问题具有最优子结构
    • 问题的最优解所包含的子问题的解也是最优的
  • 问题具有无后效性
    • 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取何种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
• 思路方法
  • 原问题分解为子问题
    • 一些问题的求解归结于它的子问题的求解，且子问题与原问题类似，只是规模减小。
    • 子问题一旦解决即被保存（通常存入一个多维数组）。
  • 确定状态
    • “状态”简介：在用动态规划解题时，我们往往将和子问题相 关的各个变量的==一组取值==，称之为一个“==状态==”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“==值==”，就是这个“状态”所对应的==子问题的解==。
    • ==状态空间与时间复杂度==：整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。（在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。）
    • 用动态规划解题，经常碰到的情况是，K个整型变量能 构成一个状态（如数字三角形中的行号和列号这两个变量 构成“状态”）。如果这K个整型变量的取值范围分别是 N1, N2, ……Nk，那么，我们就可以用一个K维的数组 array[N1] [N2]……[Nk]来存储各个状态的“值”。这个 “值”未必就是一个整数或浮点数，可能是需要一个结构 才能表示的，那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解。
  • 确定一些初始状态（边界状态）的值
  • 确定状态转移方程
    • 将第一步 分解 得到的原问题与子问题的关系用数学符号语言表述出来，即实现状态之间的转移关系。
• 动规程序写法
  • 记忆递归型
    • 递归函数+记忆数组
  • “人人为我”递推型
    • 1,2,3,...,n-1 => n
    • 递推到“n”时“n”仍未被求出，前面已被求出的状态值用于求“n”的状态值
  • “我为人人”递推型
    • n => k (k>n)
    • 递推到“n”时“n”已经被求出，n将用于求后面的状态值

动规中递归法向递推法转化的一般方法：

• 递归函数有n个参数，就定义一个n维的数组，数组 的下标是递归函数参数的取值范围，数组元素的值 是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。

常见分解（状态转移）方法归纳

• 多分类讨论， 想想解决原问题等同于解决什么和什么。有时候要经过多层分解才能够得到与原问题结构相同的子问题。
• “n=(n-1)+1”型与"n=1+(n-1)"型（与 递归 的 先走一步 思想又异曲同工之妙，n为问题规模）
• "F(i,j,k)=F(i-1,j,k)+F(i,j-1,k)+F(i,j,k-1)"型（这里拿 三维 的情况举例，其他维度的状态转移方程与此大同小异）
• "F(m,n)=A, A=G( F(m-1,n),F(m,n-1) )"型，间接递归

附注

1. 数字三角形题目启示录：
   ①空间优化：滚动数组（通过覆盖今后无用的旧有数据空间的方法来压缩空间），降维，关注不必要的存储空间以及运行过程中变得可以丢弃的数据。②递归化递推：逆向思维。

算法基础笔记

原文：https://www.cnblogs.com/BAIDI-HOME/p/12247623.html