dy.cpp

#include <iostream>
#include <vector>
using namespace std;
struct meet
{
    int left, right, value;
};

// opt[i] = v[i] + opt[prev[i]]
// opt[i] = opt[i-1] 
// 递推公式
int solve(vector<meet> &mm, int i, vector<int> &prev) {
    static vector<int> memory_solution(i+1, -1); // 已经计算过的最优解结果， 存起来利用， 避免重复计算。
    cout<<"i is "<< i <<endl;
    if(memory_solution[i] != -1) {
	    cout<<"i is "<< i << " calulate before, return result "<< memory_solution[i]<<endl;
	    return memory_solution[i];
    }
    if(i == 0) return mm[i].value;
    int not_selected = solve(mm, i-1, prev); // 不选当前任务 i 的能赚的钱
    int prev_opt = 0;
    if(prev[i] != -1) {
	prev_opt = solve(mm, prev[i], prev);
    }else{
	prev_opt = 0;
    }
    int selected = mm[i].value + prev_opt; // 选当前任务 i 的能赚的钱
    memory_solution[i] = max(selected, not_selected);
    return memory_solution[i];
} 
int main()
{
    vector<meet> mm {
         {1,4,5}, {3,5,1},
         {0,6,8}, {4,7,4}, {3,8,6}, 
         {5,9,3}, {6,10,2}, {8,11,4} };
    int n = mm.size();
    vector<int> prev(n, 0); 
    cout<<endl<<"--- prev -- "<<endl;

   // 先计算prev， 也就是选了当前i 的任务后，之前只能做哪个i 了
    for(int i=n-1; i>0; --i) {
        int j = i;
        while(j > 0) {
        	if(mm[i].left < mm[j].right) {
        		j--;
        	}else {
        		break;
        	}
        }
        if(j==0 && mm[i].left < mm[0].right)
        	prev[i] = -1;
        else
        	prev[i] = j;
    }
    for(auto it : prev){ cout << it<<" "; }
    cout<<endl<<"--- prev -- "<<endl;
    int ret = solve(mm, n-1, prev);
    cout<<"ret is "<<ret<<endl;
    return 0;
}