2021-01-04

动态规划：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

初始化 base case dp[0][0][...] = base

进行状态转移 for 状态1 in 状态1的所有取值：

状态table dp[][] 即状态转移的数组，考虑是否可以进行空间压缩，变成O(1)。如果当前状态仅由前面O(1)个状态转移过来，则可以用状态压缩进行迭代。

leetcode-fib数列-easy

堆排序：小顶堆为例

核心算法：1:creat_heap  2:adjust

creat_heap 通过从第一个非叶子结点开始调用adjust直到到达根结点。

adjust 通过寻找叶子结点的最小值，查看是否根结点小于叶子结点，不是则交换。如果交换，则需要对被交换结点进行再一次判断，直到叶子结点。如果小于则不交换

void adjust(vector<int>& res,int n,int i,int high) {

while (i < high) {

find min;

if (res[i] > res[min_index]) {

    swap(res[i], res[min_index]);

   }

    i = min_index;

}