没想到考试考到了huffman树，就赶紧来写写。
1、什么是huffman树（不具体讨论huffman树的定义，在这里就放两张图看看）
上图便是两种构造不同的huffman树
2、huffman树的求法
(1).dp做法
相信很多人都会想到贪心的方法，但dp也要拿来说说。
设dp[i][j]表示前i个点,还空出来j个叶子节点的值。那么转移便有两种。
a.将i号点直接放在叶子节点上，即dp[i][j] = dp[i+1][j-1]
b.将剩下的叶子节点都扩展出两个节点来，就是把剩下的元素的深度向下移了一格，即dp[i][j*2] = dp[i][j] + a[i+1]到a[n]的和。
最后的ans = min( ans , dp[n][k] ).
(2).贪心做法
贪心的方法比较简单，就像合并果子一样，取出两个最下的进行合并就好了。
3、总结：关键是dp到贪心的转化，题目可以考与huffman树类似的dp方程，但能否将dp转化为贪心便是解题的关键。
转载于:https://www.cnblogs.com/Gaxc/p/9872975.html
