动态规划初探：选定总价值之和最高的工作

在bilibili看了别人关于动态规划的基础介绍讲的挺好，容易理解。
建议看完视频再看代码，加深理解。
重要的是掌握DP的思想: 将大问题划分为小的子问题, 多找一下例题和代码，多看，多想。

视频中以一个题目为例：

给定不同工作的时间及其价值（工作时间会有重叠），选定总价值之和最高的工作，且同一时间只能进行一个工作。

这里我直接给出代码，看完视频，代码就比较简单了。
直接看前两个for中的解算部分就好，print的内容只是帮助理解~
写代码的时候注意细节，比如 vector<int> opt(n + 1, 0);， 还有solving DP的时候 索引meeting（day)数组要-1，我在注释里也写了喔0-0

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

struct Meeting
{
    int begin;
    int end;
    int val;
};

int maxValueMeeting(vector<Meeting> &day) {
    
    int n = day.size();
    vector<int> opt(n + 1, 0);  // n+1
    vector<int> pre(n + 1, 0);

    for (int i = 1; i < n + 1; i++)
        for (int j = i - 1; j >= 1; j--) 
            if (day[i - 1].begin >= day[j - 1].end)  //  i-1, j-1.
            {
                pre[i] = j;
                break;
            }

    for (int i = 1; i < n + 1; i++)
    {
        opt[i] = max(day[i-1].val + opt[pre[i]], opt[i - 1]);    // day[i-1]
    }

    /************************************************************************/
    /* print i's max value && pre choice, if pre[i] == 0, i not a choice     */
    /************************************************************************/
    for (int i = 0; i < n + 1; i++)
        cout << i << '\t' << opt[i] << '\t' << pre[i] << endl;


    /************************************************************************/
    /*                print meeting choice                                  */
    /************************************************************************/
    cout << "Meeting choice: ";
    int i = n;
    int last;
    while (i > 0) { 
        if (pre[i] == 0) {
            i--;
        }
        else {
            cout << i << "<-";
            i = pre[i];
            last = i;
        }
    }
    cout << last << endl;

    //return result
    return opt.back();
}

// test
int main()
{
    vector<Meeting>today = { 
        {1, 4,5},
        {3, 5, 1}, 
        {0, 6, 8},
        {4, 7, 4},
        {3, 8, 6},
        {5, 9, 3},
        {6, 10, 2},
        {8, 11, 4}
    };
    
    cout << "today max Meeting Value： " << maxValueMeeting(today) << endl;
}

我的输出：

0       0       0
1       5       0
2       5       0
3       8       0
4       9       1
5       9       0
6       9       2
7       10      3
8       13      5
Meeting choice: 8<-4<-1
today max Meeting Value： 13