algorithms

introduce 动态规划是通过组合子问题的解来解决整个问题，不同与分治算法，动态规划的子问题不是相互独立的， 动态规划通过对每个子子问题只计算一次来优化计算过程。 动态规划一般用于最优化问题求解. 一般步骤 描述最优解结构 递归定义最优化解的值, 定义递归式(最重要的一部) 按自底向上的方式计算最优解 构造一个最优解(一般不需要，或第三部已经保留了过程) 能应用动态规划的两个主要特征 问题包含最优子结构,父问题的最优解需要子问题的最优解 子问题重叠，应用动态规划可以提高性能 动态规划的变形: 备忘 自顶向下的计算策略. 使用低效但是容易理解的递归算法，同时对子问题解进行缓存。 TODO实例1: 生产线问题 TODO实例2: 矩阵乘法 TODO实例3: 最长公共子序列 TODO实例4: 编辑距离

heap sort in-place sort algorithms O(nlgn) 过程要点 left/right/parent可以通过(2n, 2n+1, n/2)算出. 一般数组索引从0开始，left/right/parent为(2n+1, 2n+2, (n-1)/2) 建堆算法 O(n) 堆有一个cap和一个len(当前长度) 步骤 # max-heap 保持堆性质 def max_heap(h, i): l = left(i) r = right(i) if l <= heap_size(A) && A[l] > A[i]: lg = l if r <= heap_size(A) && A[r] > A[i]: lg = r if lg != i: A[i], A[lg] = A[lg], A[i] max_heap(h, lg) # build-heap 建堆 def build_heap(h): hs = len(h) for i = hs/2; i >= 0; i--: build_heap(h, i) # heap-sort 排序 def heap_sort(A): build_heap(A) for i = len(A); i>0; i--: A[0], A[i] = A[i], A[0] A.