目录

 

集合中的三种关系

等价关系举例

相容关系举例

偏序关系举例

等价类的定义

等价关系与等价类的例题

商集的定义

集合中的三种关系

等价关系：设R为定义在集合A上的关系，若R是自反的，对称的，传递的，则R称为等价关系

相容关系：设R为定义在集合A上的关系，若R是自反的和对称的，则R称为等价关系

序关系（偏序关系）：设A是一个集合，若A上的关系R是自反的，反对称的，传递的，则R是A上的偏序关系

等价关系举例

等价关系可以简单理解成我们实数集上的等于关系，等于关系应该算等价关系的子集。

当然，离散数学中也对等价关系做了抽象，比如实数集上的同余模k关系。

再抽象一点，比如通信基站之间的通信关系，通信基站A可以和自己通信（类似于我们在调试的时候在地址栏输入localhost回环地址）【自反性】，基站A可以和相邻的基站B通信，那么基站B也能和基站A通信（正常情况下）【对称性】，基站A可以和基站B通信，基站B可以和基站C通信，那么基站A通过B的中转也能和基站C通信（同样是正常情况下）【传递性】。

相容关系举例

集合A={cat, teacher, cold, desk, knife, by}

定义关系r = {<x, y> | x, y∈A 且 x和y有相同的字母}

那么r是一个相容关系。

自己和自己有相同的字母【自反性】，如果A和B有相同的字母，那么B和A也有相同的字母【对称性】

偏序关系举例

设A是正整数m=12的因子集合，设≤为整除关系，求COVA

A = {1， 2， 3， 4， 6， 12}

“≤” = {<1, 2>, <1,3>, <1,4>, <1,6>, <1,12>, <2,4>, <2, 6>, <2, 12>, <3, 6>, <3, 12>, <4, 12>, <6, 12>, <1, 1>, <2,2>, <3, 3>,     <4, 4>, <6,6>, <12, 12>} 

在求覆盖集之前我先说一下为什么求覆盖集，可以说求覆盖集是画哈斯图的准备工作。由于偏序关系具有反对称性，所以哈斯图可以用无向图来表示偏序关系，又由于偏序关系的传递性，所以我们在画哈斯图的时候可以不用画多余的传递边，这些传递边的消去就是覆盖集的工作内容

COVA = {<1,2>, <1,3>, <2,4>, <2,6>, <3,6>, <4,12>, <6,12>}

哈斯图如下



等价类的定义

设R为集合A上的等价关系，对任何a∈A，集合 [a]R={x | x∈A， aRx} 称为元素a形成的R的等价类

由于等价关系满足对称性，所以也可以将定义写成 [a]R={x | x∈A， xRa}

等价关系与等价类的例题

例题一：设I为整数集，R={<x, y> | x mod y=k}，证明R是等价关系

证明： 对于任意 a，b，c∈I，有

1）因为 a-a = k*0， 所以 <a, a>∈R，R满足自反性

2）假设 a mod b = k，即有 a-b=kt ， 那么 b-a=-kt ， 所以<b, a>∈R， R满足对称性

3）假设a mod b = k 且 b mod c = k，即 a-b=kt， b-c=ks，那么有 a-b+b-c=k(t+s) ，即 <a, c>∈R， R满足传递性

综上所述，得证R是等价关系

例题二：设关系R为整数集I上的模3同余关系，求R的等价类

解：由例题一已经得证R是等价关系，对于模3同余关系，一共有三个等价类

[0]R = {... , -6, -3, 0, 3, 6, ...}

[1]R = {..., -5, -2, 1, 4, 7, ...}

[2]R = {..., -4, -1, 2, 5, 8, ...}

例题三：求证给定集合A上的等价关系R，对于a，b∈A，有aRb，当且仅当 [a]R=[b]R

证明：假设 [a]R=[b]R，因为 a∈[a]R, 所以a∈[b]R, 即有aRb

反之，若 aRb，则有 c∈[a]R => aRc => cRa => cRb => c∈[b]R

所以有 [a]R 包含于 [b]R,

同理可证 [b]R 包含于 [a]R

所以有 [a]R=[b]R

得证

商集的定义

对于集合A上的等价关系R，其等价类的集合称为商集，比如例题二中的商集 I/R={ [0]R, [1]R, [2]R }

动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间。 

理解动态规划并不需要数学公式介入，只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的，才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系，以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路，如果有需要的话再补充吧。 

动态规划是对于 某一类问题 的解决方法！！重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推！ 

怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）

当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！ 

太抽象了还是举个例子吧： 

比如说我想计算第100个非波那契数，每一个非波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每计算一个新状态所需要的时间也是常数且状态是线性递增的，所以时间复杂度也是线性的。 

上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。 

非波那契那个例子过于简单，以至于让人忽视了阶段的概念，所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。非波那契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。想象另外一个问题情景，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。 

现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下：

假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。 

好消息是，有时候我们并不需要真的计算所有状态，比如这样一个弱智的棋盘问题：从棋盘的左上角到达右下角最短需要几步。答案很显然，用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态，正如这个问题中走n步可以走到很多位置一样。但是同样n步中，有哪些位置可以让我们在第n+1步中走的最远呢？没错，正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像？所以计算的方法是递推。 

既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。 

如果一个阶段的最优无法用前一个阶段的最优得到呢？ 

什么你说只需要之前两个阶段就可以得到当前最优？那跟只用之前一个阶段并没有本质区别。最麻烦的情况在于你需要之前所有的情况才行。 

再来一个迷宫的例子。在计算从起点到终点的最短路线时，你不能只保存当前阶段的状态，因为题目要求你最短，所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变，之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态，根据这些信息才能计算出下一个状态！ 

每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。哦哦，刚刚提到的之前的路线会影响到下一步的选择，这个令人不开心的情况就叫做有后效性。 

刚刚的情况实在太普遍，解决方法实在太暴力，有没有哪些情况可以避免如此的暴力呢？ 

契机就在于后效性。 

有一类问题，看似需要之前所有的状态，其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索，进而引出动态规划的思路。 

假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢？需要从头到尾依次枚举是否选择当前的数字，每选定一个数字就要去看看是不是满足“上升”的性质，这里第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。哈哈，依稀出现了刚刚迷宫找路的影子！咦慢着，每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较就行了！这是和之前迷宫问题的本质不同！这就可以纵容我们不需要记录之前所有的状态啊！既然我们的选择已经不受之前状态的组合的影响了，那时间复杂度自然也不是指数的了啊！虽然我们不在乎某序列之前都是什么元素，但我们还是需要这个序列的长度的。所以我们只需要记录以某个元素结尾的LIS长度就好！因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的，然后就得到了DP方程 

LIS(i)=max{LIS(j)+1} {j< i && a[j] << a[i]}

所以一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！

每个阶段只有一个状态->递推；

每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；

每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到 

这个性质叫做最优子结构；

而不管之前这个状态是如何得到的 

这个性质叫做无后效性。

另：其实动态规划中的最优状态的说法容易产生误导，以为只需要计算最优状态就好，LIS问题确实如此，转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值，然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包（阶段）容量为j时（状态）计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。

依照这种描述：假若你的问题的结论包含若干决策，则可以认为从初始状态（边界条件）到解中间的决策流程是一个决策状态空间中的转移路线。前提是：你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的点，且转移路线包含所有可能的路径。这个描述是包含动态规划两大条件的。 
所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了； 
最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。 

最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。这样的描述下，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。于是乎，对于动态规划，他的本质就是图论中的最短路；阶段可以去除，因为不一定有明确的阶段划分。

根据上面的这些对动态规划问题的定义，我们可以知道，解决动归的问题问题，需要定义好问题的状态，最好的办法就是以问题本身需要求的结果作为状态的定义，然后确定这个状态是否满足最优子结构和无后续性，如果满足就可以使用DP求解了，如果不满足就按照之前说的，如果你发现一个状态转移有后效性，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加状态转移的描述就可以了

下面举一道LeetCode的hard级的DP问题，很难想到，参考的别人的博客： 

题目链接： 
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/ 

根据问题的描述，我可以定义一个状态global[i][j]，表示当前到达第i天可以最多进行j次交易，最好的利润是多少，从状态的定义来看这个状态是无后效性的（可以由global[i-1][j]的状态得到而不用考虑global[i-1][j]是怎么得到的），但是它不具有最优子结构（第i天j次交易的情况没有覆盖到），global[i][j]是下一个状态的值，我们当前并不知道，所以我们还需要增加状态local[i][j]来表示第i天完成第j次交易时的最好利润是多少。 

所以得到global[i][j]的状态转移方程：global[i][j]=max(local[i][j],global[i-1][j])，还需要更新local[i][j]。 

根据local[i][j]的定义，我们可以知道只有两种状态可以得到local[i][j]，即 

前i-1天未完成第j次交易，第i天完成，或者前i-1天完成了交易，改到第i天完成第j次交易 

diff表示，第i天和第i-1天的价格差 

1、未完成第j次交易，global[i-1][j-1]+max(diff,0)  表示diff如果为正，那么我应该在第i天卖完成第j次交易 

2、完成了第j次交易，local[i-1][j]+diff  表示第i-1天卖出，变到第i天卖出，并不增加交易次数 

具有最优子结构且无后效性。

AC代码：节省空间复杂度，从后往前刷，利用滚动数组

public int maxProfit(int[] prices) {  
    if(prices==null || prices.length==0)  
        return 0;  
    int[] local = new int[3];  
    int[] global = new int[3];  
    for(int i=0;i<prices.length-1;i++)  
    {  
        int diff = prices[i+1]-prices[i];  
        for(int j=2;j>=1;j--)  
        {  
            local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);  
            global[j] = Math.max(local[j],global[j]);  
        }  
    }  
    return global[2];  
}  

接口
接口与抽象类不同，它是一种规范，犹如USB、PCI接口规范一样。

接口与抽象类一样都不能创建实例，必须由接口的实现类完成对象的创建工作。

接口与抽象类的区别如下：

接口的数据成员必须是静态常量；抽象类可以有非常量的数据成员。
抽象类在体现父子继承关系时，是“is-a”的关系，即父类与子类在本质上是应该 相同的；接口不要求实现类是本质上的相同，而是按照接口的规定实现契约，是 “like-a”的关系，一般而言接口很多用于系统对外部的扩展。
继承特性也不太一样：一个类只能实现一个抽象类，但可以实现多个接口。

接口的定义
语法格式如下：
 [public]  interface  接口名称  [extends 父接口列表]{   
 	[public] [static] [final] 数据类型  常量名=常量； //定义常量   
 	[public] [abstract] 返回值类型  方法名称([参数列表])；  //定义抽象方法   
 	[public] static 返回值类型 方法名称([参数列表]){ //定义静态方法    
 		…  …   
 	}   
 	[public] default  返回值类型 方法名称([参数列表]){  //定义默认方法   
 		 …  …   
 	}  
 }  

五个关键点：

数据成员是静态的，必须赋初值的，是作为一个常量的；
数据成员默认为 public static final；
抽象方法默认为 public abstract；
静态方法的修饰符static不能省略，默认方法的修饰符default不能省略；
接口中的成员都是public的。

接口的实现与引用
与抽象类一样，接口不能用于创建对象；要想创建接口的对象，必须使用接口的实现类。

语法如下：
class 类名称  implements 接口列表{
   … … 
}  

五点说明：

如果实现接口的类不是抽象类，则该（实现）类必须实现接口中所有的抽象方法；
实现类在实现接口的抽象方法时，方法头必须与接口的方法头完全相同，否则就是 在定义一个新方法；
接口中的抽象方法都显式的或隐式的定义为public，在类的实现方法前必须显式的 使用public修饰符，否则系统将警告缩小了该方法的访问权限；
每个接口在编译时都会生成一个.class字节码文件；
接口类型是引用类型。

举例：

package ch08; 
interface IShape{  //编译完成后会产生一个名为Ishape.class文件  
	final double PI=3.14;  
	abstract double getArea();  
	abstract double getLength(); 
} 
class Circle implements IShape{ //编译完成后会产生一个名为 Circle.class文件  
	double radius;  
	public Circle(double r){   
		radius=r;  
	}  
	public double getArea(){   
		return PI*radius*radius;  
	}  
	public double getLength(){   
		return 2*PI*radius;  
	} 
} 
class Rectangle implements IShape{ //编译完成后会产生一个名为 Rectangle.class文件  
	private double width;  
	private double height;  
	public Rectangle(double width,double height){   
		this.width=width;   
		this.height=height;  
	}  
	public double getArea(){   
		return width*height;  
	}  
	public double getLength(){   
		return 2*(width+height);  
	} 
} 
public class Demo{ //编译完成后会产生一个名为 Demo.class文件  
	public static void main(String[] args){   
		IShape circle=new Circle(5.0); //用接口的实现类创建接口对象   
		System.out.println("PI="+IShape.PI);  //接口的静态常量直接用接口调用   
		System.out.print("圆面积="+circle.getArea());   
		System.out.println("；周长="+circle.getLength());   
		Rectangle rect =new Rectangle(6.5,10.8);   
		System.out.print("矩形面积="+rect.getArea());   
		System.out.println("；周长="+rect.getLength());  
	} 
} 

第一范式

存在非主属性对码的部分依赖关系 R(A,B,C) AB是码 C是非主属性 B-->C B决定C C部分依赖于B

第一范式

定义：如果关系R 中所有属性的值域都是单纯域，那么关系模式R是第一范式的

那么符合第一模式的特点就有

1)有主关键字

2)主键不能为空，

3)主键不能重复,

4)字段不可以再分

例如：

 StudyNo   |   Name   |   Sex   |   Contact

20040901      john         Male      Email:kkkk@ee.net,phone:222456

20040901      mary         famale    email:kkk@fff.net phone:123455

以上的表就不符合，第一范式：主键重复(实际中数据库不允许重复的)，而且Contact字段可以再分

所以变更为正确的是

 StudyNo   |   Name   |   Sex   |      Email         |      Phone

20040901      john         Male       kkkk@ee.net       222456

20040902     mary          famale      kkk@fff.net      123455

 

第二范式

存在非主属性对码的传递性依赖 R(A,B,C) A是码 A -->B ,B-->C

定义：如果关系模式R是第一范式的，而且关系中每一个非主属性不部分依赖于主键，称R是第二范式的。

所以第二范式的主要任务就是

满足第一范式的前提下，消除部分函数依赖。

StudyNo   |   Name   |   Sex   |         Email         |      Phone    |   ClassNo  | ClassAddress

01                  john        Male       kkkk@ee.net     222456      200401            A楼2

01                   mary       famale    kkk@fff.net       123455      200402            A楼3

这个表完全满足于第一范式,

主键由StudyNo和ClassNo组成，这样才能定位到指定行

但是,ClassAddress部分依赖于关键字(ClassNo-〉ClassAddress),

所以要变为两个表

表一

StudyNo   |   Name   |   Sex   |      Email         |      Phone |   ClassNo

      01            john         Male       kkkk@ee.net  222456   200401     

      01           mary         famale    kkk@fff.net    123455      200402    

表二

 ClassNo  | ClassAddress

 200401      A楼2

 200402      A楼3


第三范式

不存在非主属性对码的传递性依赖以及部分性依赖 ，

StudyNo   |   Name   |   Sex   |      Email         |      bounsLevel   |   bouns

20040901      john         Male       kkkk@ee.net   优秀                    $1000

20040902     mary         famale    kkk@fff.net       良                         $600

这个完全满足了第二范式,但是bounsLevel和bouns存在传递依赖

更改为：

StudyNo   |   Name   |   Sex   |      Email         |      bouunsNo

20040901      john         Male       kkkk@ee.net   1

20040902     mary         famale    kkk@fff.net       2

bounsNo   |   bounsLevel   |   bouns

1                   优秀                $1000

 2                 良                   $600

这里我比较喜欢用bounsNo作为主键，

基于两个原因

1）不要用字符作为主键。可能有人说：如果我的等级一开始就用数值就代替呢？

2）但是如果等级名称更改了，不叫 1，2 ，3或优、良，这样就可以方便更改，所以我一般优先使用与业务无关的字段作为关键字。

 

一般满足前三个范式就可以避免数据冗余。