动态规划：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
初始化 base case dp[0][0][...] = base
进行状态转移 for 状态1 in 状态1的所有取值：
状态table dp[][] 即状态转移的数组，考虑是否可以进行空间压缩，变成O(1)。如果当前状态仅由前面O(1)个状态转移过来，则可以用状态压缩进行迭代。
堆排序：小顶堆为例
核心算法：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;
}
网友评论