一名宅。

首页 > 算法

理解动态规划思想

前言 最近和朋友聊天，说起DP问题，想到大学时候学长上来一通“状态转移函数”把我们讲懵了，于是尝试写个入门笔记。 DP思想 通俗来说，动态规划解决问题的方法，就是当系统处于任何一个状态C，你去穷举所有状态A，然后把可能从A到达C的情况全部找出来，并从中获得最优解即可。所以，所谓的“状态转移方程”就是存在一条边从状态A到状态C，这条边的代价。简而言之，动态规划主要思想就是自底向上、局部最优到全局最优，通过计算每个子结构的最优解，求出总体结构的最优解。其目的是解决通过自顶向下的算法（如递归），带来的子结构重复计算，导致时间复杂度指数级上升的问题。 入门示例 桌上有 1kg、8kg、11kg...

A*算法

Dijkstra就是A*的一个特例 先占坑 这周写 概述 A*算法是一种深度优先遍历，是Dijkstra算法的一种优化算法。该算法从一个指定的点开始创建一棵树，每步延伸一次这棵树的节点，直到这棵树的某一条路径抵达重点。在每一步操作时，A*算法需要决定它的哪一个部分子路径需要进行延伸 其他 由于A*算法判断不能到达的方式是穷举掉所有的路径，所以在游戏寻路算法中，通常不能到达的点计算量会非常大。所以在实际使用时，通常把不能互相到达的点提前标记好，寻路算法在计算前先判断两个点之间是否可以连通。

哈夫曼编码

毕业多年发现写业务写废了，需要重新捡回算法。 概念 哈夫曼编码是利用哈夫曼树生成的编码方式，其特点是编码长度最短，常用于数据压缩。哈夫曼树是带权路径总长度最小的树，又称为最优二叉树，所谓最优二叉树是指所有叶子节点的带权路径和最小的树。树中一个节点的带权路径就是该点的权值乘以其到根节点的距离。 即： WPL = W1 * L1 + W2 * L2 + ... + Wn * Ln 生成 从节点集合S中取出权值最小的两个节点a,b作为左右子节点建立二叉树T，并从S中删除a,b 将二叉树T的根节点重新加入集合S，其权值为a,b权值相加 重复前两步操作直至集合S为空，此时得到的二叉树即为...

STL模板不同类型在内存分布与效率上的差别

最近发现虽然一直在使用STL，但从来没有好好的去了解对比过，所以决定系统的学习与归纳下STL相关知识。 关键字： vector,list,map,set,unordered_map,unordered_set Vector Vector在内存上的分布是采用一段连续内存来存储，进行插入操作时如果内存不足则会malloc申请一块新的内存并将当前数据memcpy复制到新内存中并free释放原内存。但是在有些实现中通过一些算法来分析申请新内存并舍弃旧内存的效率，当效率底下时会通过使用链表连接两块内存来存储数据，当然这部分对外是不透明的，外部使用时只会看到Vector是一整块内存空间。 对Ve...

最新文章

最近回复