动态规划 Dynamic Programming

分而治之也是存在前提的。 分而治之是一种递归
问题可以分，分出来的规模也差不多。分出来的问题，是彼此不相关的，相互独立的。可以分而治之。
但是存在一些不是相互独立 的子问题。会造成相互通讯的工作量爆炸。呈指数级别增加。
但是动态规划能够有效发现这类问题，把重复的工作节省下来。
DP是把递归的思路反向变为递推。最优化子结构。#也是一种贪心

Fibonacci:recursion

斐波那契数列。每隔一个月就可以开始生兔子。
fib(n)=fib(n-1)+fib(n-2) 0 1 1 2 3 5 8 13

int fib(n){ return (2>n) ? n : fib(n-1)+fin(n-2) ; }

考量计算的速度
递归实例recursion instance。如果直接用上述代码会存在很多的重复duplicate。递归基会被更频繁的调用。
算法的复杂度：$T(n)=T(n-1)+T(n-2)+1>2\cdot T(n-2)+1=\mathcal{O}\left((\sqrt{2}{)}^n\right)$
$T(n)=T(n-1)+T(n-2)+1=\mathcal{O}(fib(n+1))=\mathcal{O}\left({\varphi }^n\right),\varphi =(1+\sqrt{5})/2=1.618\dots$
时间复杂度会存在指数爆炸。封底估算，back of envelope。
一般的主频 GHz —— 一秒计算10^9 。大概算43项fibonacci需要一秒钟。

解决办法：
Memoization 该单词为记忆化。少了r 是计算机所特有的单词。
LOOK-UP table 做一个查询表 1维的array。每一次divide后，先查表确定是否计算过。

T M[N]; 

def f(n)
	if(n==1) return trivial(n); //递归基
	if(M[n]==UNDEFINED)
		M[n] = f(n-X) + f(n-Y)*f(n-Z); //存储
	else ...//返回查表所得的值
return M[n];

power 计算幂

问题的规模 计算a^ n 所需要复杂度 Naive O(n) DP O(logn) r=logn为分解形成的位数
快速幂算法

int power(int a, int n){
	int pow = 1, p = a;
	while(0 < n){
		if(n&1)
			pow *= p
		n>>=1;
		p *= p ;
	}
	return pow;
}

(矩阵算法在理论上也可以采用快速幂。)
fibonacci 数列也可以利用矩阵乘法进行求解,但是在实际上行不太通
$$\begin{array}{l}\mathcal{A}=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]=\left[\begin{array}{cc}fib(0)& fib(1)\\ fib(1)& fib(2)\end{array}\right]\\ {\mathcal{A}}^n=\left[\begin{array}{cc}fib(n-1)& fib(n)\\ fib(n)& fib(n+1)\end{array}\right]\end{array}$$

SPU Shortest Path Upward

从下往上走 每一次只有三种选择，往上面或者相邻的。

最优路径可能只有一条，也可能不止一条最优路径。
法一：分而治之，但是效率很低。
从最上面那一层开始做选择。为寻找第k层某一个最小值，需要在在第k-1层的L左M中R右中寻找最小的路径，再加上当前的weight。
$d^k(i)=w^k(i)+\min \left\{d^{k-1}(i-1),d^{k-1}(i),d^{k-1}(i+1)\right\}$
但是也会存在大量的重复。因为第k层存在左右相邻的点会重复唤醒k-1层的两个节点。平均而言每一行的递归实例会重复三次。因此相当于fibonacci，会存在指数爆炸的问题
法二：解决重复的问题方法。DP
记忆化或者把计算顺序颠倒过来。先计算出第k层的点最小路径，对第k+1层的三个任务提供了新的思路。
第一层：trivial case 第一层的解可以直接得到。然后逐渐推到第二层第三层

LMP Longest Manhattan Road 最长曼哈顿道路

从一个左上角，走到右下角。希望去到最大的权值。但是不能走回头路。权重最大格路模型
分而治之，每一个任务可以分为上面那个和左边那个，从这两个中取一个最大值。但存在重复唤醒。 也是一种指数爆炸。
动态规划，把递归改成递推。从左上角出发，给下一个提供方案，每次更新最优的权重。

LCS：longest common subsequence最长公共子序列

给出一对子序列，在一对子序列中寻找按顺序相同的最长公共序列。
但是最长公共子序列可能会有多个。有时仅计算最长公共子序列的长度，避免歧义。

减而治之
对比末尾元素是否相同，有一定概率他们是一样的，就可以在这个地方把他们切下来。
若他们真的一样就把他们decrease。
若最后两个字符不相等，就可以把原来的子任务分解为两个子任务，一个裁掉尾字符，一个保留尾字符。一共两种情况分解下去。此处采用了divide and conquer。再进行递归。
每一个格子有两到三种情况。三种:最后一个字符相等。二种:最后一个字符不等。注意也会存在重复和指数爆炸的情况。

动态规划
转而采用递推！找到最优化子结构，每个点向三个方向延伸。从起始点出发，类似于沿对角线的广度优先遍历。
也可以一行一行的遍历过去。如果是从主对角线延展过去的话，则需要将max上加一。 如果仅仅是简单从上面和左面继承过去，那么就不需要将max加一。
这个对角线也会存在一些歧义性。也就是最长公共子序列并不唯一。

背包问题

此处先讨论 01背包问题
v是指物品的价值 w是指可以选择的物品重量 当然希望v越大w越小 存在一个W的上限。问最优的方案
贪心？先把最大或者最小的那个带进去。都不能够解决这个问题
分而治之？m[i][W] 在前 i 项物品中，允许装w个重量。
区别在于第i项物品是否需要安装。
如果没有安装进去的话，则为正上方的m[i-1][W]。表示在前 i-1 项物品中，允许装w个重量。
如果第i项物品确实安装进去了，只考虑前i-1项物品，重量第w列移动至第w-wi列。m[i-1][W-Wi]
选择这两个 m[i-1][W]，m[i-1][W-Wi] 中更加大的那个。注意这种递归也会造成大量的爆炸。
但是递归也提供了解决这个问题的子结构。

动态规划
从第一行开始往下算。以填表递推的方式往下计算。 就是所谓的DP。但是时间复杂度比较高。
因为item有 n个 w在最大的W处。。算法复杂度不会低于O(n*W)。实际上做了一点个简化，将其w，item简化为整数。W是很难控制的。

背包问题也存在变式。
如果每种item都有好几个。是一种01背包的变种。

传递闭包 Transitive Closure Definition

考量一个有向图(digraph)中的可到达性。
reachable 能够通过有限步到达的都是称之为可达到的。可以直接或者间接地到达的。
随机生成一个矩阵。
演示过程中新增的点，就是可以间接达到的。中间的必须要经过一些桥梁。
以k为桥梁，u->k,k->v 即u-v。在矩阵中，u-v左侧为u-k。下侧为k-v。
每一个单元都可以看作一个子问题。取决于有没有两个相通的节点。
若采用递归，也会存爆炸问题。

采用动态规划
哪一点，如果作为桥梁，可以给哪些点提供桥梁。
选择方法：从第一行第一列以第0点作为桥梁开始，以一个十字架构往下挪动。将可以间接到达的点标记为1。

for k in range(0,n) //k作为一个桥梁，开始循环
	for u in range(0,n)
		for v in range(0,n)
			A[u][v] = A[u][v] || A[u][k]&&A[k][v]
		//	程序写到这里其实已经可以了，下面两句可以替代上面两句
		if A[u][k]  //但是如果采用这一步更快 如果计算机支持64位运算，
			A[u]= A[u]|A[k] // | 表示按位或

最短路径 任何两点 All-Pair Shortest

for k in range(0,n) //k作为一个桥梁，开始循环
	for u in range(0,n)
		for v in range(0,n)
			A[u][v] =min( A[u][v] , A[u][k]+A[k][v] )

UK&KV 这两个距离之和提供了一条新的通路。比较原有的和新的选取最小的。每次都会求出最短路径。