第一章 随机事件的概率

1.1 随机事件与样本空间

1. 随机试验 —>（每一个结果） 基本事件 $e₁, e₂, …, eₙ$ —>（属于） 随机事件 A, B, C

   • 必然事件 S 或者 $\Omega$
   • 不可能事件 ∅
2. 样本空间：事件的全部基本事件组成的集合，记为 S 或 Ω

3. 常见运算 ：

   • $ A \subset B \quad A = B $
   • $ A + B (=) A \cup B $
   • $ AB (=) A \cap B $
   • 互斥 $ A \cap B = \varnothing $
   • 对立事件 $ AB = \varnothing, A + B = S $
   • $ A - B $

阅读全文

线性DP：递推方程有明显的线性的顺序。
考虑两个问题：如何状态表示（集合+属性）、如何状态计算（划分状态转移集合）
T1：

状态表示： 记录所有从起点走到(i,j)的路径中的路径数字之和的最大值。
状态计算：f[i,j] = max(f[i-1][j], f[i-1][j-1]) + a[i,j]
需要注意需要把f[i,j]初始化为极小值，避免算到三角形右边的元素。

T2：最长上升子序列

状态表示：使用一维数组，f[i]表示以第i个数结尾的上升子序列的长度的最大值。
状态计算：计算f[i]，去看倒数第二个数是哪个数，共i种可能，以编号1、2、3、……、i-1结尾或原本没有数（记为0）。每个循环先看是否满足上升的条件，若满足，则这个f[i]_j = f[j]+1，最后计算一个最大的f[i]_j就得出了f[i]的值。
时间复杂度计算：状态数量 × 转移的数量。此时是$n^2$。

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[N], f[N];

int main(){
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        f[i] = 1; //先全部赋值为1，只有a[i]一个数
        for(int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

如何保存最长序列？
创建一个数组g[i]，存储每个转移是怎么转移过来的（记录上一个状态的id，也就是找f[i,j]最大值时找到的位置）。

阅读全文

本章主要介绍动态规划的常用思路，并介绍了背包问题里面的01背包、多重背包的解题思路和代码

01背包

01背包问题为：给定背包总体积，给N个物品，每个物品有一个体积和重量，只能用一次或不用，问最大重量是多少？
下面是思路，定义函数f(i,j)代表：仅包含前i个物品且总体积小于等于j的背包的最大价值是多少，故最终需要的结果是f(N,V)。
初始时把所有值都设为0，且i或j等于0的本身值就为0。
对于一个新的状态f(i,j)，可能的值有下面两种可能，如果包含i，则答案为f(i-1，j-vi) + wi；如果不包含i，则为f(i-1,j)。这两个值取最大值就可以算出f(i,j)。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i=1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i=1; i <= n; i++)｛
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    ｝
    cout << f[n][m] << endl;
}

阅读全文

继承

继承使用关键词extends，继承格式为class Son extends Father{}。
Java不支持多继承（一个类同时继承自好几个类），支持多重继承、不同类继承同一个类。

特性

• 子类会继承父类的非private的属性和方法；
• 子类可以添加自己新的属性和方法；

• 子类可以重写/实现父类的方法/抽象方法；

  继承关键字

  extends关键字： 继承自某一个父类；
  implements关键字： 继承接口；
  super和this： super用于实现对父类成员的访问，比如在实现子类的构造方法时可以直接调用super(可有参数)来完成父类的构造；this是自己的引用，常用于方法或者构造方法里，若方法里的传参有和类中相同名字的参数，使用this.name = name可以实现调用，如果没有相同的参数，直接使用名字就能完成操作，不需要this；

阅读全文

参考：黑马程序员（Bilibili） and 菜鸟教程

基础知识

1. 所有的Java程序都从入口public static void main(String[] args)进入，字段分别为访问修饰符、关键子、返回类型、方法名、（输入变量）。
2. 文件名要与public class的类名相同。

3. 命令行运行方法：

   javac HelloWorld.java //编译为class文件
   java HelloWorld //运行class文件

4. 注释：单行注释//，多行注释/*注释*/

5. 变量类型：
   

阅读全文