霍夫曼树的构造是使用了变长编码来减少数据所占空间，一般我们只考虑前缀码，即没有任何码字是其它码字的前缀。

我们的构造过程如下所示：

这里我们根据上述表示，我们每次总是“贪心”的选择两个最小的值来求和，并插入队列中。所以我们可以构造一个最小优先队列来存储各字母的频率。算法代码如下：

//
//  main.cpp
//  HUFFMAN
//
//  Created by LZH on 2017/11/4.
//  Copyright © 2017年 LZH. All rights reserved.
//

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef struct BitNode
{
    int frep;
    struct BitNode *left;
    struct BitNode *right;
}Node;

//定义比较结构
struct cmp1{
    bool operator ()(int &a,int &b){
        return a>b;//最小值优先
    }
};
//构造霍夫曼树
void HUFFMAN(int c, priority_queue<int, vector<int>, cmp1> &que1)
{
    int n = c;
    for (int i=0; i<n-1; i++) {
        Node *newNodeZ = (Node*)malloc(sizeof(Node));
        Node *newNodeX = (Node*)malloc(sizeof(Node));
        Node *newNodeY = (Node*)malloc(sizeof(Node));
        newNodeX->frep = que1.top();
        que1.pop();
        newNodeY->frep = que1.top();
        que1.pop();
        newNodeZ->left = newNodeX;
        newNodeZ->right = newNodeY;
        
        newNodeZ->frep =newNodeX->frep + newNodeY->frep;
        que1.push(newNodeZ->frep);
    }
}

int main() {
//    priority_queue<int> que; //构造优先队列
    int b[6] = {9,5,12,13,16,45};
//    vector<int> a(b,b+6);
    priority_queue<int , vector<int>, cmp1 >que1; //最小优先队列
    for (int i=0; i<6; i++) {
        que1.push(b[i]);
    }
    HUFFMAN(6, que1);
    while (!que1.empty()) {
        cout<<que1.top()<<' ';
        que1.pop();
    }
    return 0;
}

最后输出为100，返回了编码树的根节点。

这个问题是一个典型的可以运用贪心算法的题目，我们在初始的选择一个活动之后，应该将之后的资源被其他任务尽量多的占用。所以我们应该第一个选择活动最快结束的活动，因为它剩下的资源可以被它之后开始的任务尽量多的使用。所以我们可以运用一种递归形式或者迭代算法来表达这个形式：

//
//  main.cpp
//  Greedy_Activity_Selector
//
//  Created by LZH on 2017/11/3.
//  Copyright © 2017年 LZH. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
void print(int n)
{
    cout<<n<<' ';
}

/**
 迭代形式函数

 @param s 活动开始时间数组
 @param f 活动结束时间数组
 @param result  用于存储结果
 */
void GREED_ACTIVITY_SELECTOR(vector<int> s , vector<int> f , vector<int> &result)
{
    int n = s.size();
    result.push_back(1);
    int k=1;
    for (int m=2; m<=n; m++) {
        if (s[m]>=f[k]) {
            result.push_back(m);
            k = m;
        }
    }
}

/**
 尾递归形式函数

 @param s 活动开始时间数组
 @param f 活动结束时间数组
 @param k 从活动k开始计算
 @param n 共有n个活动
 @param result 用于存储结果
 */
void RECURSIVE_ACTIVITY_SELECTOR(vector<int> s,vector<int> f, int k, int n, vector<int> &result)
{
    int m = k+1;
    while (m<=n && s[m]<=f[k]) {
        m++;
    }
    if (m<=n) {
        result.push_back(m);
        RECURSIVE_ACTIVITY_SELECTOR(s, f, m, n ,result);
    }
}

int main() {
    int a[12] ={0,1,3,0,5,3,5,6,8,8,2,12};
    int b[12] ={0,4,5,6,7,9,9,10,11,12,14,16};
    vector<int> s(a,a+12);
    vector<int> f(b,b+12);
    vector<int> result;
    RECURSIVE_ACTIVITY_SELECTOR(s, f, 0, 11, result);
    GREED_ACTIVITY_SELECTOR(s, f, result);
    for_each(result.begin(),result.end(),print);
    return 0;
}

其中递归形式的流程如下图所示：

但两种算法运行时间类似都为\(\Theta(n)\)

与动态规划的不同

贪心算法通过做出局部最优来构造全局最优解。换句话说，直接做出在当前问题下看起来最优的选择，而不必考虑子问题的解。

在动态规划中，每个步骤都要进行一次选择，但选择通常依赖于子问题的解，因此，我们通常以自底向上的方式来求解动态规划问题，先求解较小的子问题，然后是较大的子问题。但是在贪心算法中，我们总是做出在当时看起来最佳的选择，然后求解剩下的唯一子问题。贪心算法进行选择时可能依赖之前做出的选择，但不依赖于任何将来的选择或者是子问题的解。所以贪心算法在进行第一次选择时不求解任何子问题，自顶向下进行逐步选择，将给定的子问题实例变小。

两者最典型的区别，可以用分数背包和0-1背包问题来举例，这里不做细说。

最长公共子序列问题（LCS）给定两个序列\(X=<{x_1,x_2,...x_m}>和Y=<y_1,y_2,...y_n>\),求X和Y长度最长的公共子序列。总共分三个步骤：

步骤一：刻画最长公共子序列的特征

步骤二：一个递归解

步骤三：计算LCS的长度

上述过程我们有如下图来表示：

步骤4 构造LCS

这里我们用C++来构造这个算法：

//
//  main.cpp
//
//  Created by LZH on 2017/10/30.
//  Copyright © 2017年 梁中豪. All rights reserved.
//


#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

//计算LCS的长度
void LCS_LENGTH(char *X ,char *Y ,int **b ,int **c ,int &m ,int &n)
{
    //    int m = sizeof(X)/sizeof(char);
    //    int n = sizeof(Y)/sizeof(char);
    
    //    int b[m][n];
    //    int c[m][n];
    
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            if (X[i]==Y[j]) {
                c[i][j] = c[i-1][j-1]+1;
                b[i][j] = 1;
            }
            else if (c[i-1][j]>=c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
    }
}

void PRINT_LCS(int **b,char *X,int i,int j)
{
    if (i==0 || j==0) {
        return;
    }
    if (b[i][j]==1) {
        PRINT_LCS(b, X, i-1, j-1);
        cout << X[i] <<endl;
    }
    else if (b[i][j]==2)
    {
        PRINT_LCS(b, X, i-1, j);
    }
    else
    {
        PRINT_LCS(b, X, i, j-1);
    }
}

int main()
{
    char X[8] = {'x','A','B','C','B','D','A','B'};
    char Y[7] = {'y','B','D','C','A','B','A'};
    int m = sizeof(X)/sizeof(char);
    int n = sizeof(Y)/sizeof(char);
    int **b =new int*[m];
    for (int i = 0; i<m; i++) {
        b[i] = new int[n];
    }
    
    int **c = new int*[m];
    for (int i = 0; i<m; i++) {
        c[i] = new int[n];
    }
    LCS_LENGTH(X,Y,b,c,m,n);
    PRINT_LCS(b,X,m-1,n-1);
    return 0;
}