0 1 1 2 3 5 8 12 ...
- 递归（重复子问题，TIL） -> 递推（空间换时间 + 记录旧纪录）
- 记忆化搜索（用数组等将已经算过的东西记录下来，在下一次要使用的直接用已经算出的值，避免重复运算，去掉的重复的搜索树）
有一人要爬n阶的楼梯，他一次可以爬1阶或2阶，问要爬完这n阶楼梯，共有多少种方法？
- 根据分类加法原理：
- 第n阶的方法 = n-1阶的方法 + n-2阶的方法
- 同样的，对于n-1阶和n-2阶我们也可以用类似的方法进行求解
f[1] = 1, f[2] = 2
f[i] = f[i-1] + f[i-2]
设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走。如图所示。
问题：当三角形数塔给出之后，求从第一层到达底层的路径最大值。
- $$f[i,j]=max(f[i-1,j],f[i-1,j-1])+a[i,j];$$
N * M 的棋盘上左上角有一个过河卒，需要走到右下角。卒行走的规则：可以向下、或者向右。现在要求你计算出卒从左上角能够到达右下角的路径的条数，
- Solutions
- 确定状态——原问题是啥？子问题是啥？
- 从(0,0)走到(n,m)的路径数
- 从(0,0)走到(i,j)的路径数
- f[i][j]表示从左上角走到 (i,j)点的路径条数,
- 确定状态转移方程和边界
- $$f[i][j] = f[i-1][j] + f[i][j-1]$$
- $$f[1][1] = 0;$$
- 考虑是否需要优化
- 确定实现方法
- [ ] #todo 扩展2.1：过河卒
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
- [ ] #todo 扩展2.2：传纸条
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。
n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。
两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。
- Solutions
- 确定状态——原问题是啥？子问题是啥？
- 原问题：从1开始传球第m步球回到1的方法数
- 子问题：从1开始传球第i步球到达j的方法数
- f[i][j]表示第i次传球之后球在第j个人手上的方法数
- 确定状态转移方程和边界
- $$f[i][j] = f[i-1][j-1] + f[i-1][j+1]$$
$$f[0][1] = 1;$$
- 注意由于是一个环，j=1 时 左边（j-1） 为n，j=n 时 右边（j+1）为1
- 考虑是否需要优化
- 确定实现方法
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中 L 是桥的长度）。青蛙从桥的起点0开始，不停的向终点L方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数（包括 S,T）。当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。 题目给出独木桥的长度 L，青蛙跳跃的距离范围 S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 M<= 100; S,T<=10, L<=10^9
- 第一步：确定状态——原问题是啥？子问题是啥？
原问题：从0开始跳到>=L的位置最少踩到的石头数
子问题：从0开始跳到i位置最少踩到的石头数
f[i]为从0跳到i的最少踩到的石头数
第二步：确定状态转移方程和边界
f[i]=min(f[i-k] + a[i]) (S≤k≤T) (a[i] 为i点的石子数)
第三步：考虑是否需要优化
时间和空间都不允许……
- 再次审视数据范围
M<= 100; S,T<=10, L<=10^9
M很小——石头很稀疏
S，T也不大——S与T不等的时候，超过一定范围的所有距离都是可以跳到的
这个一定范围是多少？？
S= 9 ，T=10 时 >=90的距离都可以表示
（S和T相等的时候只需要看S的倍数有多少石头）
Michael喜欢滑雪，这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
- 第一步：确定状态——原问题是啥？子问题是啥？
f[i][j]表示从（i，j）滑下的最长路径长度
第二步：确定状态转移方程
——由于f[i][j]由上下左右四个方向转移过来
F[i][j] = max {f[i - 1][j] + 1 (a[i - 1][j] <a[i][j])
{f[i + 1][j] + 1 (a[i + 1][j] <a[i][j])
{f[i][j - 1] + 1 (a[i][j - 1] <a[i][j])
{f[i][j + 1] + 1 (a[i][j + 1] <a[i][j])
（初值）：f[i][j] = 0
第三步：考虑是否需要优化
第四步：确定实现方法
相信同学们已经看出问题了，我们没法通过递推的方式在算f[i][j]之前将他上下左右四个点的值都求出来！！！
设有一个正整数的序列：b1,b2,…，bn，对于下标i1<i2<…＜im，若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。
例如，下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15
对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存在长度为5的不下降序列。
但是，我们看到还存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i5＝10，i6=11，i7=12，i8=13，满足：7＜9＜16＜18
＜19＜21＜22＜63，则存在长度为8的不下降序列。
问题为：当b1,b2,…，bn给出之后，求出最长的不下降序列。
- 第一步：确定状态——原问题是啥？子问题是啥？
F[i] 前i个数的最长不下降子序列——求不了啊~!为什么求不了？
不知道这个序列的最后一个元素是哪个，没法转移
F[i]以第i个数为结尾的最长不下降子序列
第二步：确定状态转移方程
f[i]=max{f[j]+1}（a[j]<=a[i] 且 j<i）
f[i] = 1
- f[i] = 1
f[i]=max{f[j]+1}（a[j]<=a[i] 且 j<i）
- 第三步：考虑是否需要优化
O(N^2)
可以使用单调队列或者线段树等数据结构优化到O（NlogN） ——留给学有余力的同学
第四步：确定实现方法
- 拓展6.1：拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输出这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。
- 认真分析一下题就会发现：每一个导弹最终的结果都是要被打的，如果它后面有一个比它高的导弹，那打它的这个装置无论如何也不能打那个导弹了，也就是说最少要打最长上升子序列长度那么多次可以打完！
- **完整覆盖一个序列的不上升子序列的个数等于这个序列的最长上升子序列的长度，**严格证明数学请参考数学中偏序集的Dilworth定理。
题意：给你一个有正有负的序列，求一个=子串（连续的一段），使其和最大！
样例输入： -5 6 -1 5 4 -7
样例输出： 14
- 第一步：确定状态——原问题是啥？子问题是啥？
f[i]前i个数的最大子串和——出现了和前一个题一样的问题
用f[i]表示一定要选第i个数的情况下前i个数的最大子串和（选第i个数和其左边连续的若干个）
第二步：确定状态转移方程
f[i] =max(f[i - 1]+a[i], a[i])
第三步：考虑是否需要优化
O（N）
第四步：确定实现方法
- 一个问题：
如果我一定要你求前i个数的最大子序列和怎么办？
- g[i] = max (f[i], g[i-1])
- 扩展7.1：不相交的两个子串的最大和
给你一个有正有负的序列，求两个不重叠的子串，使其和最大！
f[i][j] 前i个数中间挑出j个子串的最大和
f[i][j] = max(f[i-1][j] + a[i], f[k][j-1]+a[i]) 0<k<i
O（N^2）
- 其实只有两个子串，为什么不枚举两个子串的分界点呢？
假如 右边那个串是从k位置开始的
我们是不是可以先求一个F’[i] 表示以i为子串最左边那个数的最大子串和
再求一个G[i]表示前i个数的最大子串和
对每个k 都计算一下F’[k]+G[k]最后取一个最大值就可以了
- 扩展7.2： 不相交的m个子串的最大和
给你一个有正有负的序列，求m个不重叠的子串，使其和最大！
f[i][j] 前i个数中间挑出j个子串的最大和
f[i][j] = max(f[i-1][j] + a[i], f[k][j-1]+a[i]) 0<k<I
O(M*N^2)
- 扩展7.3：最大子矩形
在一个矩阵中找到一个子矩阵，该子矩阵和最大！！输出最大和即可。
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
- 枚举行（子矩形从第i行到第j行，i和j都要枚举）
然后把第i行到第j行压成一行
然后求最大子串和
给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。
样例输入：abcfbc
abfcab
样例输出：4
- 第一步：确定状态——原问题是啥？子问题是啥？
f[i][j]表示前一个字符串的前i位与后一个字符串的前j位的最长公共子序列长度
第二步：确定状态转移方程
当x[i]==y[j]，f[i][j]=f[i-1][j-1]+1
当x[i]!=x[j]，f[i][j]=max(f[i - 1][j] ,f[i][j - 1])
a[1]==b[1] f[1][1] = 1
else f[1][1] = 0
第三步：考虑是否需要优化
第四步：确定实现方法
- 拓展8.1：回文词
回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。
- 分析：假定我们已经先原串中找到了一个最长回文串，然后对于原串中不属于这个回文串的字符，在它关于回文串中心的对称位置添加一个相同字符。那么需要添加的字符数量即为 ：n-最长回文串长度。
最长回文串对称轴前的每一个字符即原串当中也都能与对称轴后的字符一一对应。如果我们将原串进行翻转，最长回文串中的字符必然会在原串和逆序串中也一一对应，所以可以通过求原串和逆序串的最长公共子序列得到最长回文串的长度!
- 拓展8.2：最长公共子序列
- 输出最长公共子序列的方案
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
如：有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1） 3*12=36 2） 31*2=62
这时，符合题目要求的结果是：31*2=62
- 第一步：确定状态——原问题是啥？子问题是啥？
f[i][j]代表前i位数中间添加J个乘号所得到的的最大乘积
第二步：确定状态转移方程
f[i][j] = max{f[k][j - 1] + num[k + 1][i]} (1 <= k < i)
num[i][j]代表第i位数到第j位数组成的数字是多少。
第三步：考虑是否需要优化
第四步：确定实现方法
-
