如何对 vector 初始化

• 大小为size的一维向量，二位向量

1
2

vector<what-type> var-name(what-size);
vector<vector<what-type>> var-name(rowSize, vector<what-type>(colSize));

• 数组转 vector

1
2
3
4
5
6
7
8
9
10
11
12

int rowSize = ?;
int colSize = ?;
what-type A_[rowSize][colSize] = {
  {element1, elment2, ..., element},
  {},
  ...
  {}
};
vector<vector<what-type>> A(rowSize, vector<what-type>(colSize));
for(int row=0; row<rowSize; row++) {
  A[row].assign(A_[row], A_[row] + colSize);
}

何为贪心？

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就作出选择（下一步的选择总是在当前看来收敛最快和效果最明显的那一个），而且一旦做出了选择，不管将来有什么结果，这个选择策略都不会改变（以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题）。
• 贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
• 贪心算法对于大部分的优化问题都能产生最优解（如单源最短路径问题，最小生成树等），但不能总获得整体最优解，通常可以获得近似最优解。
• 贪心策略一旦经过证明成立后，它就是一种高效的算法。

并查集

• 并查集：并查集处理的是集合之间的关系，即 union，find。在这种数据类型中，N个不同元素被分成若干个组，每组是一个集合，这种集合叫做分离集合。并查集支持查找一个元素所属的集合和两个元素分别所属的集合的合并。注意：并查集只能进行合并操作，不能进行分割操作。
• 并查集支持以下操作：
  • makeset(x)：创建一个仅包含 x 的独立集合（分离集）；最初每个节点单独构成了一个分离集 ==> 一组分离集
  • find(x)：不断重复地检验节点对，判断其是否属于同一个集合？
  • union(x, y)：每当增加了一条边，将与之相关的两个集合合并。

　所谓 回文（palindrome），指的是正读和反读都是一样的。而 字符子串 和 字符子序列 的区别，在前面 算法设计与分析[0011] Dynamic Programming(III)（Longest Common Subsequence） 中也有提到过，字符字串指的是字符串中连续的n个字符，而字符子序列指的是字符串中不一定连续但先后顺序与原字符串一致的n个字符。

　　子序列和子字符串的不同之处在于，子序列不需要是原序列上连续的字符。对于 Longest Common Substring 以及 Longest Common Subsequence 这类题目，大多数需要用到 DP 的思想，其中，状态转移是关键。

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

• 给出一个序列 $a_1, a_2, …, a_n$，求它的一个子序列（设为 $s_1, s_2, …, s_n$ ），使得这个子序列满足这样的性质：$ s_1 < s_2 < s_3 <…< s_n $ 并且这个子序列的长度最长，输出这个最长的长度。实际上，诸如最长下降子序列，最长不上升子序列等问题都可以看成同一个问题，仔细思考就会发现，这其实只是 $<$ 符号定义上的问题，并不影响问题的实质。

　本文通过 53. Maximum Subarray & 152. Maximum Product Subarray 分析根据动态规划思路进行问题求解中的一个关键环节：子问题的拆分和求解。

　本文通过 Unique Paths [I] & [II] 两道题从普通的递归思路到动态规划两种方式的求解尝试，希望能够初步分析如何根据动态规划的思路，进行问题求解。