geekTime_basicMath4Programmers

笔记：极客时间-程序员的数学基础课(黄申)

• 001

  • 假设现在需要设计一个抽奖系统。需要依次从 10 个人中，抽取三等奖 3 名，二等奖 2 名和一等奖 1 名。请列出所有可能的组合，需要注意的每人最多只能被抽中 1 次。

• 002

  • 动态规划：求编辑距离，由一个字符串转成另一个字符串所需的最少编辑操作次数，我们就叫作编辑距离。

• 003

  • 动态规划： 钱币组合。有2，3，7三种面额的纸币。凑够m(100)元，最少钱币数的方案

• 004

  • 树的构建和深度优先搜索： 构建个字典并搜索

• 005

  • 图：构造一个人际关系图，广度搜索。

• 006

  • 图：构造一个人际关系图，双向广度搜索，找出两个人之前最短通路。

• 007

  • 图：狄克特斯拉算法 Dijkstra， 无负权边加权图找最快路径。（地图导航）
    • Dijkstra 算法的核心思想是，对于某个结点，如果我们已经发现了最优的通路，那么就无需在将来的步骤中，再次考虑这个结点。
    • 如果边的权重都是正值，那么通路上的权重之和是单调递增的，所以其它通路的权重之和一定大于当前的最小权重，也就是即使存在其它通路，其权重也会比当前最小值大。